Task 9. The Federation of Wrestling has assigned each participant in the competition a qualification number. It is known that in matches between wrestlers whose qualification numbers differ by more than 2, the wrestler with the lower number always wins. The tournament for 512 wrestlers is held on an Olympic system: at the beginning of each day, the wrestlers are divided into pairs, the loser is eliminated from the competition (there are no draws). What is the highest qualification number that the winner can have?
Answer: 18.

Solution. Note that a wrestler with number $k$ can only lose to a wrestler with number $k+1$ or $k+2$, so after each round, the smallest number cannot increase by more than 2 numbers. In a tournament with 512 participants, there are 9 rounds, so the number of the tournament winner does not exceed $1+2 \cdot 9=19$.

Suppose the wrestler with number 19 can win. Then in the first round, the wrestlers with numbers 1 and 2 must be eliminated. This is only possible if the wrestler with number 1 loses to the wrestler with number 3, and the wrestler with number 2 loses to the wrestler with number 4. Thus, after the first round, the wrestlers with numbers 3 and 4 will remain. Similarly, after the second round, the wrestlers with numbers 5 and 6 will remain, after the third round - 7 and 8, ..., after the eighth round - 17 and 18. This means that in the final, decisive battle, the wrestlers with numbers 17 and 18 will meet. Contradiction with the assumption that the wrestler with number 19 can win.

We will show that the wrestler with number 18 can win. Let's call the wrestlers with numbers greater than 18 weak. Suppose in the round with number $k \leqslant 8$ the wrestler with number $2 k-1$ loses to the wrestler with number $2 k+1$, the wrestler with number $2 k$ loses to the wrestler with number $2 k+2$, the wrestlers with numbers $2 k+3, \ldots, 18$ win against some weak wrestlers, and the remaining weak wrestlers play among themselves. Then after 8 rounds, the wrestlers with numbers 17 and 18 will remain, and in the final battle, the wrestler with number 18 will win.