Tanya and Serezha have a heap of $2016$ 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?
Problem
Source:
Tags: combinatorics, Combinatorial games
ManuelKahayon
22.07.2016 17:36
First, we will ignore the fact that this is a health-unfriendly game due to the risks of diabetes. Then, the answer is Tanya. Tanya will always eat 1 candy at a time. Since this leaves an odd number of candies for Serezha, Serezha is forced to eat another candy, leaving Tanya with an even number of candies. Tanya repeats this process until there are 4 candies left, then afterwards she eats two of the candies. Now, Serezha is forced to eat one candy, then Tanya eats the remaining candy. Serezha loses (but wins in terms of health condition).
celilcelil
09.07.2021 12:01
Tanya wins. Tanya takes $1$ dollar and leaves odd number dollar and Serezha forced to remove $1$ dollar. Tanya does until reach $4$. At this moment she removes $2$ dollar and at anyway ( divide $2$ or minus $1$) Serezha leaves $1$ dollar and Tanya removes it and wins. 2016 $\mapsto$ 2015 $\mapsto$ 2014 $\mapsto$...$\mapsto$ 5 $\mapsto$ 4 $\mapsto$ 2 $\mapsto$ 1 $\mapsto$ 0.