LX OM - I - Task 12

Given a prime number $ p $. On the left side of the board, the numbers $ 1, 2, 3, \cdots, p - 1 $ are written,
while on the right side, the number $ 0 $ is written. We perform a sequence of $ p - 1 $ moves, each of which proceeds
as follows: We select one of the numbers written on the left side of the board, add it to all the
remaining numbers on the board, and then erase the selected number.
Determine for which values
of $ p $ it is possible to choose the numbers in such a way that the number remaining on the board after
all moves have been performed is divisible by $ p $.
Answer: For all prime numbers $p$ except 2 and 3.
Let $ t_i $ for $ i=1,2, \cdots,p-1 $ denote the initial value of the number that
was erased from the board in the $ i $-th move. Thus, the sequence $ (t_1,t_2,t_3, \cdots,t_{p-1}) $ is a permutation
of the sequence $ (1,2,3, \cdots,p-1) $ and uniquely determines the way the erased numbers are chosen in subsequent moves.
Let us introduce the notation

We will prove by induction that after the $ i $-th move, all numbers on the board are greater
by $ s_i $ than their initial values.
Indeed: this statement is true for $ i = 1 $, since in the first move the number
$ t_1 $ was erased, increasing all other numbers by $ s_1 = t_1 $. If, however, after
the $ i $-th move all numbers on the board were greater by $ s_i $ than their initial values,
then in particular the number initially equal to $ t_{i+1} $ had the value
$ t_{i+1} + s_i $ after the $ i $-th move. Therefore, as a result of the $ (i+1) $-th move, the amount
$ t_{i+1} + s_i $ was added to all remaining numbers. Since the numbers were greater by $ s_i $ than their initial values after the $ i $-th move,
they became greater by $ t_{i+1}+s_i+s_i $ than their initial values after the $ (i+1) $-th move.
It remains to observe that

which completes the inductive proof. We have thus shown that after all $ p $ moves, the number
remaining on the right side of the board is

We have thus reduced the problem to finding all prime numbers $ p $ for which there exists a permutation
$ (t_1,t_2,t_3, \cdots,t_{p-1}) $ of the sequence $ (1,2,3, \cdots,p-1) $ such that the number (1) is divisible by $ p $.
We directly check that for $ p=2 $ and $ p=3 $ it is not possible to obtain a number divisible by $ p $:
for $ p = 2 $ the number (1) is $ 1 $, and for $ p = 3 $ it can be $ 1+2\cdot 2=5 $ or $ 2+2\cdot 1 = 4 $.
We will show that if $ p $ is a prime number greater than $ 3 $, then for the permutation

formed from the sequence $ (1,2,3,4, \cdots,p - 2,p - 1) $ by swapping the positions in pairs $ (2j-1,2j) $ for
$ j \geqslant 2 $ and then reversing the order, the number (1) is divisible by $ p $.
Indeed, for the permutation (2), the number (1) has the value

For $ j =2,3, \cdots, \frac{1}{2}(p-1) $, the relation

holds, from which it follows that $ L = M - N $, where $ M $ is the sum of numbers of the form $ 2^{i-1}i $ for
$ i =1,2, \cdots,p-1 $, and $ N =2^2 +2^4 +2^6 + \cdots +2^{p-3} $. Using the formula for the sum of consecutive
terms of a geometric sequence, we calculate that

and

Thus,

By Fermat's Little Theorem (see LI Mathematical Olympiad, Main Committee Report,
Warsaw 2001, Appendix A, p. 102), the number $ 2^{p-1} -1 $ is divisible by $ p $. Since $ p $
is a prime number greater than $ 3 $, the fraction appearing on the right side of relation (3) is divisible by $ p $. Therefore, the right side of this relation is divisible by $ p $, which completes
the solution of the problem.