1. In a tennis tournament, 512 schoolchildren are participating. 1 point is awarded for a win, and 0 points for a loss. Before each round, pairs are formed by lottery among participants with the same number of points (those who do not find a pair are awarded a point without playing). The tournament ends as soon as a sole leader is determined. How many schoolchildren will finish the tournament with 6 points?
Answer: 84.

Solution. We will show that in a tournament with $2^{n}$ participants, no one will score points without playing, and for any $k \in\{0, \ldots, n\}$, exactly $C_{n}^{k}$ participants will end up with $k$ points. We will use induction on $n$. For $n=1$, this is obvious. Suppose that for some $n$ both statements are true. Then, in a tournament with $2^{n+1}$ participants, after the first round, $2^{n}$ students will have 0 points and $2^{n}$ students will have 1 point. We will continue to conduct the draw so that participants from these groups only meet each other. By the inductive hypothesis, this is always possible, and such an assumption clearly does not affect the distribution of points. In other words, we are conducting two independent tournaments with $2^{n}$ participants each. By the inductive hypothesis, in the first tournament, $C_{n}^{k}$ students will score $k$ points, and in the second tournament, $-C_{n}^{k-1}$ students will score $k$ points, since all participants started with one point. In the end, $C_{n}^{k}+C_{n}^{k-1}=C_{n+1}^{k}$ students will score $k$ points (we used the main identity of Pascal's triangle). Thus, the inductive step is completed. It remains to note that $C_{9}^{6}=\frac{9 \cdot 8 \cdot 7}{1 \cdot 2 \cdot 3}=84$.