1. In an arm wrestling tournament, $2^{n}$ athletes participate, where $n$ is a natural number greater than 7. One point is awarded for a win, and zero points for a loss. Before each round, pairs are formed by drawing lots among participants with the same number of points (those who do not find a pair are simply given a point). After the seventh round, it turned out that exactly 42 participants had 5 points. What is $n$?
Answer: 8.

Solution. Let $f(m, k)$ be the number of participants who have scored $k$ points after $m$ rounds. We will prove by induction on $m$ that

$$
f(m, k)=2^{n-m} \cdot C_{m}^{k}, \quad \text { where } 0 \leqslant k \leqslant m \leqslant 2^{n}
$$

If $m=0$, then $k=0$, and $f(0,0)=2^{n}$. We will now perform the inductive step. Suppose that for some $m<n$ the required equality holds. Then each group with the same number of points contains an even number of participants, so all participants can be paired. After the $(m+1)$-th round, the groups of athletes with no wins and no losses will be halved. Therefore,

$$
f(m+1,0)=\frac{1}{2} f(m, 0)=\frac{1}{2} \cdot 2^{n-m}=2^{n-(m+1)} \cdot C_{m+1}^{0} \quad \text { and } \quad f(m+1, m+1)=\frac{1}{2} f(m, m)=2^{n-(m+1)} \cdot C_{m+1}^{m+1}
$$

Now let $k \in\{1, \ldots, m\}$. After the $(m+1)$-th round, $k$ points will be scored by those who had $k$ points and lost, as well as by those who had $k-1$ point and won. Therefore,

$$
f(m+1, k)=\frac{1}{2} \cdot f(m, k)+\frac{1}{2} \cdot f(m, k-1)=2^{n-m-1}\left(C_{m}^{k}+C_{m}^{k-1}\right)=2^{n-(m+1)} \cdot C_{m+1}^{k}
$$

(in the last transition, we used the main identity of Pascal's triangle). Thus, the inductive step is completed. It remains to note that

$$
42=f(7,5)=2^{n-7} \cdot C_{7}^{5}=2^{n-7} \cdot \frac{7 \cdot 6}{2}=42 \cdot 2^{n-8}, \quad \text { that is } n=8 .
$$