Problem 5. (5 points) In a tournament, 55 boxers participated, and after each match, the winner left the tournament. The matches were held consecutively. It is known that in each match, boxers whose difference in the number of victories (at that moment) was no more than 1, met. How many matches could the winner of the tournament have played at most?
Solution. The winner has played at most 8 matches.

Let $u_{k}$ denote the $k$-th Fibonacci number ( $u_{1}=u_{2}=1, u_{k}=u_{k-1}+u_{k-2}$ for $k \geq 3$ ). We will prove by induction that:

a) if the winner has played at least $n$ matches, then there are at least $u_{n+2}$ participants;

b) there exists a tournament with $u_{n+2}$ participants in which the winner has played $n$ matches.

The base case of the induction $\left(n=1, u_{3}=2\right)$ is obvious.

a) Let the winner A have met boxer B in the last match. The remaining matches can be divided into two tournaments: one won by A and the other by B. In the first tournament, A has played at least $n-1$ matches, so the number of participants is at least $u_{n+1}$. In the second tournament, the winner B has played at least $n-2$ matches, since the difference in the number of wins between A and B is no more than 1. Therefore, the second tournament has at least $u_{n}$ participants, and the total number of participants is at least $u_{n+1}+u_{n}=u_{n+2}$.

b) It is sufficient for the winner of a tournament with $u_{n+1}$ participants, who has played $n-1$ matches, to meet the winner of a tournament with $u_{n}$ participants, who has played $n-2$ matches, in the final match.

Since $55=u_{10}$, the answer to the problem follows from this.