Browse · MathNet
Print62nd Ukrainian National Mathematical Olympiad, Third Round, Second Tour
Ukraine counting and probability
Problem
Fedir and Mykhailo have three piles of stones: the first contains stones, the second , the third . They are playing a game with the following rules: they move in turns, in his turn a player chooses any two piles of stones, containing, say, and stones correspondingly, and takes from each of them the number of stones equal to the greatest common divisor of numbers and . The winner is the player, after whose move some pile becomes empty for the first time. Who wins if Fedir moves first, and both try to win?
Solution
Let's provide the winning strategy for Mykhailo. Suppose that before Fedir's move, the piles contained stones for some integer . Then there are 3 possible moves.
If he takes first two piles, then, as , after his move we will have the following numbers of stones: . After this Mykhailo chooses the last two piles, and as , after his move the numbers will be: . This is the initial configuration.
If Fedir chooses first and the third piles, then, as , after his move we will have the following configuration: . Mykhailo chooses last two piles once again, and gets the configuration again.
If Fedir chooses the second and the third piles, then from , we see that after his move we will have the following configuration: . In this situation Mykhailo just takes first two equal piles and wins, as after his move there will be two empty piles: .
The initial configuration is just . After the moves of Fedir and Mykhailo we will get the configuration for (or Mykhailo will win). And so on. After moves, unless Mykhailo has already won, we will have . Fedir will change it to one of: , or . It's easy to see that in all of them Mykhailo wins in the next move.
If he takes first two piles, then, as , after his move we will have the following numbers of stones: . After this Mykhailo chooses the last two piles, and as , after his move the numbers will be: . This is the initial configuration.
If Fedir chooses first and the third piles, then, as , after his move we will have the following configuration: . Mykhailo chooses last two piles once again, and gets the configuration again.
If Fedir chooses the second and the third piles, then from , we see that after his move we will have the following configuration: . In this situation Mykhailo just takes first two equal piles and wins, as after his move there will be two empty piles: .
The initial configuration is just . After the moves of Fedir and Mykhailo we will get the configuration for (or Mykhailo will win). And so on. After moves, unless Mykhailo has already won, we will have . Fedir will change it to one of: , or . It's easy to see that in all of them Mykhailo wins in the next move.
Final answer
Mykhailo (the second player) wins.
Techniques
Games / greedy algorithmsInvariants / monovariantsGreatest common divisors (gcd)