Maths Olympiad Prep

Library / /15 of 20

Number theory Difficulty 6.4 National olympiad Prove it Greece

Let p2p \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++ap110p1, 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 p2,5p \neq 2, 5, then by Fermat's Theorem we have
p10p11p(10p12)21p(10p121)(10p12+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(10p121)p|(10^{\frac{p-1}{2}}-1) or p(10p12+1)p|(10^{\frac{p-1}{2}}+1). We have two cases:

(α) If p(10p12+1)p|(10^{\frac{p-1}{2}}+1). Then at the first move Angelo plays zero at ap1a_{p-1}. Then, each time that Vangelis puts aia_i at the ii-th position, Angelo plays symmetric (i.e. at j=i+p12j=i+\frac{p-1}{2} if 0ip320 \le i \le \frac{p-3}{2}, or at j=ip12j=i-\frac{p-1}{2} if p12ip2\frac{p-1}{2} \le i \le p-2) putting the digit aia_i at the jj-th position.
Then,
10j10i(modp)aj10j=ai10jai10i(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 paj10j+ai10ip|a_j 10^j + a_i 10^i. We observe that after Angelo's first move, it remains to fill p1p-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=910i(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 910i(mod p)9 \cdot 10^i (\text{mod } p), then the total sum equals
M=i=0p32910i=10(p1)/210(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(10p121)p|(10^{\frac{p-1}{2}}-1). Then, at the first move Angelo plays 00 at ap1a_{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+p12j=i+\frac{p-1}{2} if 0ip320 \le i \le \frac{p-3}{2}, or at j=ip12j=i-\frac{p-1}{2} if p12ip2\frac{p-1}{2} \le i \le p-2) putting the digit 9ai9-a_i at jj-th position.

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 and solution reproduced as published; topic and difficulty added by this site.