On a table, there is a certain number $N$ of candies. Aline and Bruna agree that, alternately, each one must eat at least one, but no more than half of the existing quantity. The one who eats the last candy wins the game. Ana always starts the game.

a) For $N=5$, which of the two has the winning position? (A winning position is one in which the player can win regardless of the sequence of moves made by their opponent.)

b) For $N=20$, which of the two has the winning position?

c) What are the values of $N$, where $100<N<200$, that give Bruna the winning position?
Solution

a) Bruna. The number of candies that should be eaten is from 1 to half of the existing amount on the table. Therefore, the winner $(V)$ must find 1 candy on the table in their last move, and for this to happen, there should have been 2 candies on the previous move for the player $(P)$, forcing her to eat only 1; before that, there should have been 3 or 4 candies on the table, so the future winner $(V)$ eats 1 or 2 candies, respectively. Thus, since the initial number of candies is 5, the first player can only eat 1 or 2, leaving 3 or 4 on the table. Therefore, the winning position is the second player, that is, Bruna.

b) Aline. The first player, Aline, should eat 9 candies, as 11 candies will remain for Bruna, who must eat from 1 to 5, and no matter how many she eats, Aline can eat a quantity of candies such that 5 remain for Bruna, and we saw from the previous item that 5 is a losing position (a situation where the opponent has the winning position).
c) 191. Since each can only eat up to half the number of candies, if a quantity $k$ is a losing position, then twice this plus one unit, $2k+1$, will also be a losing position, because no matter how many are eaten, the opponent can leave $k$ candies on the table. Since we saw that 2 is the last losing position, as well as 5, in the first item, the sequence of losing positions is

$$
\{2, 5, 11, 23, 47, 95, 191, 383, \ldots\}
$$

that is, for Bruna to win, it is necessary that the game starts with a quantity corresponding to a losing position, and the only value in the range of 100 to 200 is 191.