RMO Training: more help from Nordic mathematical contest

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 $C_{i}$ be the candidate who lost to the gold medalist in round i. Now, let $C_{1}$ and $C_{2}$ play, the winner play against $C_{3}$ , and so forth. After 4 matches, we know the silver medalist; assume this was $C_{k}$ .

Now, the third best player must have lost against the gold medalist or against $C_{k}$ or both. (If the player had lost to someone else, there would be at least three better players.) Now, $C_{k}$ won k-1 times in the elimination rounds, the 5-k players $C_{k+1}\ldots C_{5}$ and if k is greater than one, one player $C_{j}$ with $j<k$ . So there are either $(k-1)+(5-k)=4$ or $(k-1)+(5-k)+1=5$ candidates for the third place. At most 4 matches are again needed to determine the bronze winners.