Maths Olympiad Prep

Library / Greece — Selection Examination /43 of 61

Greece — Selection Examination

Number theory Difficulty 6.4 National Olympiad Prove it Greece

Let p≥2p \ge 2 be a prime number. Angelo and Vangelis play in turns the following game: At the board there are pp empty boxes, the one next to other, and in each move, the current player puts a digit in one of the boxes. Angelo plays first and the game ends after all boxes are filled and we get a pp-digit number MM, in which we allow zeros in the beginning. The goal of Angelo is to make the number MM divisible by pp, and the goal of Vangelis is to prevent this. Prove that Angelo has a winning strategy.

Solution

M=a0+a1p+⋯+ap−110p−1, M = a_0 + a_1 p + \dots + a_{p-1} 10^{p-1},
where aia_i is the value that the ii-th box will take (from right to left).
If p=2p = 2 or p=5p = 5, then Angelo puts 00 in the last box and wins.
If p≠2,5p \neq 2, 5, then by Fermat's Theorem we have
p∣10p−1−1⇔p∣(10p−12)2−1⇔p∣(10p−12−1)(10p−12+1) p|10^{p-1}-1 \Leftrightarrow p|(10^{\frac{p-1}{2}})^2-1 \Leftrightarrow p|(10^{\frac{p-1}{2}}-1)(10^{\frac{p-1}{2}}+1)
so p∣(10p−12−1)p|(10^{\frac{p-1}{2}}-1) or p∣(10p−12+1)p|(10^{\frac{p-1}{2}}+1). We have two cases:

(α) If p∣(10p−12+1)p|(10^{\frac{p-1}{2}}+1). Then at the first move Angelo plays zero at ap−1a_{p-1}. Then, each time that Vangelis puts aia_i at the ii-th position, Angelo plays symmetric (i.e. at j=i+p−12j=i+\frac{p-1}{2} if 0≤i≤p−320 \le i \le \frac{p-3}{2}, or at j=i−p−12j=i-\frac{p-1}{2} if p−12≤i≤p−2\frac{p-1}{2} \le i \le p-2) putting the digit aia_i at the jj-th position.
Then,
10j≡−10i(modp)⇒aj10j=ai10j≡−ai10i(modp) 10^j \equiv -10^i \pmod{p} \Rightarrow a_j 10^j = a_i 10^j \equiv -a_i 10^i \pmod{p}
so p∣aj10j+ai10ip|a_j 10^j + a_i 10^i. We observe that after Angelo's first move, it remains to fill p−1p-1 positions, which is an even number. Matching as above, Angelo can make the number divisible by pp.

10j=10i(mod p)⇒aj10j+ai10i=(ai+aj)10i=9⋅10i(mod p) 10^j = 10^i (\text{mod } p) \Rightarrow a_j 10^j + a_i 10^i = (a_i + a_j) 10^i = 9 \cdot 10^i (\text{mod } p)
In the above matching we get sums of the form 9⋅10i(mod p)9 \cdot 10^i (\text{mod } p), then the total sum equals
M=∑i=0p−329⋅10i=10(p−1)/2−1≡0(mod p), M = \sum_{i=0}^{\frac{p-3}{2}} 9 \cdot 10^i = 10^{(p-1)/2} - 1 \equiv 0 (\text{mod } p),
and thus Angelo wins.

(β) If p∣(10p−12−1)p|(10^{\frac{p-1}{2}}-1). Then, at the first move Angelo plays 00 at ap−1a_{p-1}. Then, each time that Vangelis puts aia_i at the ii-th position, Angelo plays symmetric with respect to the center of the number (i.e. j=i+p−12j=i+\frac{p-1}{2} if 0≤i≤p−320 \le i \le \frac{p-3}{2}, or at j=i−p−12j=i-\frac{p-1}{2} if p−12≤i≤p−2\frac{p-1}{2} \le i \le p-2) putting the digit 9−ai9-a_i at jj-th position.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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