Olympiad Maths Prep

Library / /15 of 15

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it Ukraine

Fedir and Mykhailo have three piles of stones: the first contains 100100 stones, the second 101101, the third 102102. 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, aa and bb stones correspondingly, and takes from each of them the number of stones equal to the greatest common divisor of numbers aa and bb. 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 (2n,2n+1,2n+2)(2n, 2n+1, 2n+2) stones for some integer n>1n > 1. Then there are 3 possible moves.

If he takes first two piles, then, as (2n,2n+1)=1(2n, 2n+1) = 1, after his move we will have the following numbers of stones: (2n1,2n,2n+2)(2n-1, 2n, 2n+2). After this Mykhailo chooses the last two piles, and as (2n,2n+2)=2(2n, 2n+2) = 2, after his move the numbers will be: (2n2,2n1,2n)(2n-2, 2n-1, 2n). This is the initial configuration.

If Fedir chooses first and the third piles, then, as (2n,2n+2)=2(2n, 2n+2) = 2, after his move we will have the following configuration: (2n2,2n,2n+1)(2n-2, 2n, 2n+1). Mykhailo chooses last two piles once again, and gets the configuration (2n2,2n1,2n)(2n-2, 2n-1, 2n) again.

If Fedir chooses the second and the third piles, then from (2n+1,2n+2)=1(2n+1, 2n+2) = 1, we see that after his move we will have the following configuration: (2n,2n,2n+1)(2n, 2n, 2n+1). In this situation Mykhailo just takes first two equal piles and wins, as after his move there will be two empty piles: (0,0,2n+1)(0, 0, 2n+1).

The initial configuration is just n=50n = 50. After the moves of Fedir and Mykhailo we will get the configuration for n=49n = 49 (or Mykhailo will win). And so on. After 4848 moves, unless Mykhailo has already won, we will have (4,5,6)(4, 5, 6). Fedir will change it to one of: (3,4,6)(3, 4, 6), (2,5,4)(2, 5, 4) or (4,4,5)(4, 4, 5). It's easy to see that in all of them Mykhailo wins in the next move.

Looking for a route rather than 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.