4. A table tennis tournament proceeds according to the following rule. In each round, if the number of participants is odd, one is randomly selected to automatically advance to the next round. The remaining participants $\mathrm{z}$ are paired by random draw. The players of each pair compete against each other, and the winner of each pair advances to the next round. Let $f(n)$ denote the number of rounds in a tournament with $n$ participants. (For example, $f(5)=3$.) Determine $f(2013)$ and find the smallest natural number $n$ for which $f(n)=f(2013)$.

## 57th Mathematical Competition for High School Students in Slovenia

Celje, April 20, 2013

## Solutions to Problems and Scoring

(April 21, 2013, $14: 53$ )
IV/4. If there are 2013 participants in the tournament, then $1+\frac{2012}{2}=1007$ participants advance to the second round. In the third round, $1+\frac{1006}{2}=504$ participants advance, and in the fourth round, $\frac{504}{2}=$ 252 participants advance. In the fifth round, $\frac{252}{2}=126$ participants advance, in the sixth round, $\frac{126}{2}=63$ participants advance, and in the seventh round, $1+\frac{62}{2}=32$ participants advance. In the eighth round, $\frac{32}{2}=16$ participants advance, in the ninth round, $\frac{16}{2}=8$ participants advance, and in the tenth round, $\frac{8}{2}=4$ participants advance. In the eleventh round, 2 participants advance to compete for the win. Therefore, $f(2013)=11$.

If there are no more than $1024=2^{10}$ participants in the tournament, then there will be at most 10 rounds. After the $j$-th round, there will be at most $\frac{2^{10}}{2^{j}}=2^{10-j}$ participants remaining. Thus, after 10 rounds, there will be at most $2^{10-10}=1$ participant remaining, and the tournament is already over. Let's calculate that $f(1025)=11$. Since $1025=1+2^{10}$, $1+2^{9}$ participants advance to the second round, $1+2^{8}$ participants advance to the third round, $1+2^{7}$ participants advance to the fourth round, and so on, up to the tenth round, in which $1+2^{1}=3$ participants advance. In the eleventh round, 2 participants advance to compete for the win. The smallest natural number $n$ for which $f(n)=f(2013)$ is therefore 1025.

## SCORING FOR THE OFFICIAL SOLUTION:

Calculation of $f(2013)=11$ 2 points

(for a correct calculation but incorrect answer, the participant receives 1 point)

Conclusion that for $n \leq 1024$, $f(n) \leq 10$ 3 points

(if the justification is missing, the participant receives at most 1 point, for calculating $f(1024)=10$)

Calculation of $f(1025)$ = 11 ........................................................ 2 points

If the value of the function $f$ is given but the calculation is missing, 1 point is deducted from the participant.

## SCORING FOR THE ALTERNATIVE SOLUTION:

![](https://cdn.mathpix.com/cropped/2024_06_07_8c492ac180897ee339acg-28.jpg?height=60&width=1633&top_left_y=1689&top_left_x=220)

Determination that $f(n)=k+1$ for $2^{k}<n<2^{k+1} \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots$ points

(if the justification is missing, the participant receives 0 points)

![](https://cdn.mathpix.com/cropped/2024_06_07_8c492ac180897ee339acg-28.jpg?height=51&width=1631&top_left_y=1842&top_left_x=218)

Answer $n=1025$ ........................................................ 1 point