In a tournament, 25 chess players are going to participate. They all play at different levels, and the stronger player always wins when they meet.

What is the minimum number of games required to determine the two strongest players?
Complexity: 5 Classes: 10,11

Example. Let's organize a tournament according to the Olympic system in five rounds: first, 12 pairs will play, then 6, then 3. Four people will remain, two pairs will play, and then the winners will play against each other. Thus, the strongest will be determined. He played no more than five games.

Since 24 people were eliminated, exactly 24 games were played. From the five (or fewer) participants who lost to the strongest, we will again select the strongest according to the Olympic system. This will require no more than four games. Therefore, 28 games are sufficient.

Estimate. We will conduct a tournament according to some scheme that allows us to determine the two strongest. It is clear that all participants, except the strongest, lost at least one game (otherwise, the strongest could not be determined). We can assume that all games are played sequentially. At each step of the algorithm, we will call the participant who has not lost to anyone yet the leader. Let the following conditions be met:

(1) when the leader plays against a non-leader, the leader always wins;

(2) when comparing two leaders, the one with more wins wins (if the number of wins is the same, the result is arbitrary).

Such outcomes of games are possible because there are no upper limits on the leader: if his strength is increased, the results of previous games will not change.

We introduce the concept of subordination to the leader. Initially, all participants are subordinate only to themselves. After a game of type (2), the loser and all his subordinates are reassigned to the new leader.

We will show by induction on $k$ that if the leader has won $k$ games, then he is subordinate to (including himself) no more than $2^{k}$ participants. For $k=0$, the leader is subordinate only to himself.

Suppose the leader, who has won $k$ games, wins again. The one he wins against has won no more than $k$ games. Therefore, both the winner and the loser are subordinate to no more than $2^{k}$ participants; when combining these two groups, we get no more than $2^{k+1}$ chess players.

Thus, in such a tournament, the strongest participant won at least five games, since in the end, he will be subordinate to $25>24$ participants. Among the five chess players who lost to the strongest, there is only one who did not lose to anyone else (otherwise, we would not know the second strongest participant). Each of the other four lost at least two games. Therefore, there were at least $24+4=28$ losses, which means that at least 28 games were played.

## Answer

28 games.

Send a comment