Browse · MathNet
PrintAustrian Mathematical Olympiad
Austria number theory
Problem
On a blackboard, there are integers not divisible by . Alice and Bob play a game. Alice starts and they alternately play the following moves: Alice chooses a number on the blackboard and replaces it with . Bob chooses a number on the blackboard and replaces it with .
Alice wins if the sum of the numbers on the blackboard is a multiple of after a finite number of steps.
Prove that Alice has a winning strategy.
Alice wins if the sum of the numbers on the blackboard is a multiple of after a finite number of steps.
Prove that Alice has a winning strategy.
Solution
Since both the problem statement and the winning condition are given in terms of divisibility by , it is sufficient to consider the numbers modulo . In the beginning, all the remainders are different from zero and Alice wins if the sum modulo becomes zero.
The moves and turn remainders into powers of the original nonzero values. Therefore, Fermat's little theorem can be applied. For and the prime number , one has So if Alice squares the same number four times in a row, then the remainder modulo is always obtained. Bob cannot do anything about it, because if Bob raises this number to the third power times, we get a result of The timing of Bob's moves does not matter, as the order of the factors in the exponent does not change anything.
Therefore, Alice can make all the remainders equal to by squaring each number four times. Then of course the sum is and Alice has won.
The moves and turn remainders into powers of the original nonzero values. Therefore, Fermat's little theorem can be applied. For and the prime number , one has So if Alice squares the same number four times in a row, then the remainder modulo is always obtained. Bob cannot do anything about it, because if Bob raises this number to the third power times, we get a result of The timing of Bob's moves does not matter, as the order of the factors in the exponent does not change anything.
Therefore, Alice can make all the remainders equal to by squaring each number four times. Then of course the sum is and Alice has won.
Techniques
Fermat / Euler / Wilson theoremsMultiplicative orderGames / greedy algorithms