Problem:
32 competitors participate in a tournament. No two of them are equal and in a one against one match the better always wins. (No tie please). Show that the gold, silver and bronze medal can be found in 39 matches.
Solution:
We begin by determining the gold medallist using classical elimination, where we organize 16 pairs and matches, then 8 matches of the winners, 4 matches of the winners in the second round, then 2-semifinal matches and finally one match making 31 matches altogether.
Now, the second best player must have at some point lost to the best player, and as there were 5 rounds in the elimination, there are 5 candidates for the silver medal. Let be the candidate who lost to the gold medalist in round i. Now, let
and
play, the winner play against
, and so forth. After 4 matches, we know the silver medalist; assume this was
.
Now, the third best player must have lost against the gold medalist or against or both. (If the player had lost to someone else, there would be at least three better players.) Now,
won k-1 times in the elimination rounds, the 5-k players
and if k is greater than one, one player
with
. So there are either
or
candidates for the third place. At most 4 matches are again needed to determine the bronze winners.
Cheers to Norway mathematicians!
Nalin Pithwa.
Reference: Nordic mathematical contests, 1987-2009.
Amazon India link: