Richard and Kaarel are taking turns to choose numbers from the set where is a prime. Richard is the first one to choose. Any number which has been chosen by one of the players can be chosen again be neither of the players. Every number chosen by Richard is multiplied with the very next number chosen by Kaarel. Kaarel wins the game if at some moment during the game the sum of all the found products is divisible by . Richard wins if this does not happen i.e. the players run out of numbers before any of the sums is divisible by . Can either of the players guarantee their victory regardless of their opponent's moves and if so, which one?
, 2020
Solution
Answer: Yes, Kaarel.
Let us split the numbers in the set to the following pairs: , , , . If Richard chooses some number , then let Kaarel choose the other number from the pair i.e. . 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 of the products are of the form . The residue of the sum of all the products is congruent to . For every natural number , we have , therefore . This must be an integer and as and are coprime, must be divisible by . Therefore, when the last number is chosen from the set, the sum of the products is divisible by .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.