Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 6.9 National olympiad Prove it Romania

Ana and Bogdan play the following turn based game: Ana starts with a pile of nn (n3n \ge 3) stones. At his turn each player has to split one pile. The winner is the player who can make at his turn all the piles to have at most two stones. Depending on nn, determine which player has a winning strategy.

Solutions — 2

Solution 1

If n=3n = 3 or n=4n = 4 Ana wins at her first move. If nn is odd, greater than 3, Bogdan will win. In this case, Ana has to start by making a pile with an even number of stones. Bogdan will split this pile into a pile with one stone and the rest into an odd pile. Ana has to make an even pile again and Bogdan continues his strategy unless he can win. The game may end in two different ways. If Ana leaves a pile of 2, one of 3 and the rest of 1, Bogdan will win by splitting the pile with 3 stones. If Ana leaves a pile of 4 and the rest of 1, Bogdan wins by splitting the 4-pile into two piles of 2 stones.

If n6n \ge 6 is even, then Ana will split the pile in 1 and n1n-1 and continue with the strategy described for Bogdan above. So, in this case, Ana will win.

Solution 2

For nn even, Ana splits the pile into two equal piles. Then, after Bogdan's move into one pile, she will make the same move in the other pile. This strategy will end up with Ana winning.

For n5n \ge 5 odd, we prove by induction that Bogdan wins by always leaving an even number of piles with 2 stones. We verify the cases n=5,7,9n = 5, 7, 9. For odd n11n \ge 11, we have two situations. If Ana splits n=a+bn = a+b, with a5a \ge 5 odd, Bogdan will split the pile with bb stones into two equal piles. If Ana moves in one of the equal piles, Bogdan will make the same move in the other pile. If Ana moves in the odd pile, Bogdan will follow the strategy provided by the induction hypothesis to end up with piles of 1 stone and an even number of piles of 2 stones. Ana might still be able to move in a pile of 2, but whenever she splits a pile of 2, so will Bogdan, leaving an even number of piles of 2 stones. If a=3a = 3, Bogdan will split b=3+(b3)b = 3 + (b - 3), where b35b - 3 \ge 5, and apply the same strategy as above.

Want a route through all this instead of 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.