Tanya and Serezha have a heap of candies. They make moves in turn, Tanya moves first. At each move a player can eat either one candy or (if the number of candies is even at the moment) exactly half of all candies. The player that cannot move loses. Which of the players has a winning strategy?
Solution
1. Initial Setup: Tanya and Serezha have a heap of 2016 candies. Tanya moves first. At each move, a player can either eat one candy or, if the number of candies is even, eat exactly half of all candies. The player who cannot make a move loses.
2. Tanya's Strategy: Tanya aims to leave an odd number of candies for Serezha after each of her moves. This forces Serezha to only be able to eat one candy on his turn, as he cannot divide an odd number by two.
3. First Move: Tanya starts by eating 1 candy from the 2016 candies, leaving 2015 candies for Serezha.
4. Serezha's Move: Serezha can only eat 1 candy because 2015 is odd, leaving 2014 candies.
5. Tanya's Next Move: Tanya eats 1 candy from the 2014 candies, leaving 2013 candies for Serezha.
6. Serezha's Move: Serezha eats 1 candy from the 2013 candies, leaving 2012 candies.
7. Continuing the Pattern: Tanya continues this strategy, always eating 1 candy and leaving an odd number of candies for Serezha. This pattern continues until the number of candies is reduced to 4.
8. Critical Point: When the number of candies is reduced to 4, Tanya eats 2 candies (since 4 is even), leaving 2 candies for Serezha.
9. Serezha's Move: Serezha can either eat 1 candy or eat half of the candies (which is 1 candy in this case), leaving 1 candy.
10. Final Move: Tanya eats the last candy, leaving 0 candies and winning the game.
Conclusion:
Tanya can always force a win by following this strategy, ensuring that Serezha is always left with an odd number of candies until the critical point is reached.
The final answer is Tanya has a winning strategy.
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.