Problem 9.8. 73 children are standing in a circle. A mean Father Frost walks around the circle clockwise and distributes candies. At first, he gave one candy to the first child, then skipped 1 child, gave one candy to the next child, then skipped 2 children, gave one candy to the next child, then skipped 3 children, and so on.

After distributing 2020 candies, he left. How many children did not receive any candies?
Answer: 36.

Solution. Let's number the children clockwise from 0 to 72. Initially, Santa Claus gives a candy to the child with number 1.

Consider the sequence of numbers $a_{n}=1+2+3+\ldots+n$, where $n=1,2,3, \ldots, 2020$. Notice that the $n$-th candy is given to the child whose number is the remainder of the division of $a_{n}$ by 73. We need to determine how many different remainders there are among these.

Consider the difference $a_{k}-a_{l}$ (for $k \geqslant l$). This is the sum of an arithmetic progression:

$$
a_{k}-a_{l}=(l+1)+(l+2)+\ldots+k=\frac{1}{2}(k+l+1)(k-l)
$$

The remainders of the division of $a_{k}$ and $a_{l}$ by 73 will coincide if this difference is divisible by 73. Since 73 is a prime number, either $k-l$ or $k+l+1$ must be divisible by 73.

First, note that all candies starting from the 74th will go to the children who have already received them in previous steps, since $k-(k-73)$ is divisible by 73, and therefore the numbers $a_{k}$ and $a_{k-73}$ give the same remainders when divided by 73. Thus, it is sufficient to consider $a_{k}$ for $k=1, \ldots, 73$.

For different natural numbers $k$ and $l$, not exceeding 73, the difference $k-l$ will not be divisible by 73. For the sum $k+l+1$ to be divisible by 73, it must be either 73 or $2 \cdot 73$. In the first case, we get $l=72-k$, where $k=1, \ldots, 71$ and $k \neq 36$, and in the second case only $k=72$ and $l=73$ (and vice versa).

This means that the same remainders will be in pairs $\left(a_{1}, a_{71}\right),\left(a_{2}, a_{70}\right), \ldots,\left(a_{35}, a_{37}\right),\left(a_{72}, a_{73}\right)$. The remainders between the pairs are different (and also different from the number $a_{36}$). In total, there are 37 different remainders.

Thus, among the 73 children, only 37 will receive candies. Therefore, 36 children will be left without candies.

## 10th grade