Baltic Way 2020 · Problem 16

Answer: Yes, Kaarel.

Let us split the numbers in the set to the following pairs: $(1, p-1)$, $(2, p-2)$, $\dots$, $\left(\frac{p-1}{2}, \frac{p+1}{2}\right)$. If Richard chooses some number $a$, then let Kaarel choose the other number from the pair i.e. $p-a$. This forces Richard to choose a number from a pair in which both of the numbers have not been chosen yet and hence Kaarel can make his desired move. The residues modulo $p$ of the products are of the form $-a^2$. The residue of the sum of all the products is congruent to $-(1^2 + 2^2 + \dots + (\frac{p-1}{2})^2)$. For every natural number $n$, we have $1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$, therefore $1^2 + 2^2 + \dots + (\frac{p-1}{2})^2 = \frac{(p-1)p(p+1)}{24}$. This must be an integer and as $p$ and $24$ are coprime, $\frac{(p-1)p(p+1)}{24}$ must be divisible by $p$. Therefore, when the last number is chosen from the set, the sum of the products is divisible by $p$.