Skip to main content
OlympiadHQ

Browse · MathNet

Print

Regional Competition

Austria counting and probability

Problem

On the occasion of the 47th Mathematical Olympiad 2016 the numbers and are written on the blackboard. Alice and Bob play the following game. Alice begins and in turns they choose two numbers and with written on the blackboard, whose difference is not yet written on the blackboard and write this difference additionally on the board. The game ends when no further move is possible. The winner is the player who made the last move. Prove that Bob wins, no matter how they play.
Solution
We consider the set of the numbers on the blackboard at the end of the game. It is clear that . Let and . We claim that . Otherwise, write with . By induction on , we have for (because no more moves are possible, these numbers must be on the blackboard). Thus , which contradicts the minimality of .

We conclude that . By induction on , we have for . This also implies that .

As numbers had been on the blackboard at the beginning of the game, the game ends after moves when all other numbers have been written. Therefore, Bob wins after move .

Techniques

Games / greedy algorithmsInvariants / monovariantsGreatest common divisors (gcd)