Maths Olympiad Prep

Library / /41 of 48

, 2020

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Baltic Way

Richard and Kaarel are taking turns to choose numbers from the set {1,,p1}\{1, \dots, p-1\} where p>3p > 3 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 pp. Richard wins if this does not happen i.e. the players run out of numbers before any of the sums is divisible by pp. Can either of the players guarantee their victory regardless of their opponent's moves and if so, which one?

Solution

Answer: Yes, Kaarel.

Let us split the numbers in the set to the following pairs: (1,p1)(1, p-1), (2,p2)(2, p-2), \dots, (p12,p+12)\left(\frac{p-1}{2}, \frac{p+1}{2}\right). If Richard chooses some number aa, then let Kaarel choose the other number from the pair i.e. pap-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 pp of the products are of the form a2-a^2. The residue of the sum of all the products is congruent to (12+22++(p12)2)-(1^2 + 2^2 + \dots + (\frac{p-1}{2})^2). For every natural number nn, we have 12+22++n2=n(n+1)(2n+1)61^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}, therefore 12+22++(p12)2=(p1)p(p+1)241^2 + 2^2 + \dots + (\frac{p-1}{2})^2 = \frac{(p-1)p(p+1)}{24}. This must be an integer and as pp and 2424 are coprime, (p1)p(p+1)24\frac{(p-1)p(p+1)}{24} must be divisible by pp. Therefore, when the last number is chosen from the set, the sum of the products is divisible by pp.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.