Skip to main content
OlympiadHQ

Browse · MathNet

Print

Selection Examination

Greece number theory

Problem

Let be a prime number. Angelo and Vangelis play in turns the following game: At the board there are 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 -digit number , in which we allow zeros in the beginning. The goal of Angelo is to make the number divisible by , and the goal of Vangelis is to prevent this. Prove that Angelo has a winning strategy.
Solution
where is the value that the -th box will take (from right to left). If or , then Angelo puts in the last box and wins. If , then by Fermat's Theorem we have so or . We have two cases:

(α) If . Then at the first move Angelo plays zero at . Then, each time that Vangelis puts at the -th position, Angelo plays symmetric (i.e. at if , or at if ) putting the digit at the -th position. Then, so . We observe that after Angelo's first move, it remains to fill positions, which is an even number. Matching as above, Angelo can make the number divisible by .

In the above matching we get sums of the form , then the total sum equals and thus Angelo wins.

(β) If . Then, at the first move Angelo plays at . Then, each time that Vangelis puts at the -th position, Angelo plays symmetric with respect to the center of the number (i.e. if , or at if ) putting the digit at -th position.

Techniques

Fermat / Euler / Wilson theoremsGames / greedy algorithms