On the table are 1999 tokens. Taking turns, Albert and Barbara must remove at least one token and at most half of the remaining tokens at the time they play. The player who leaves a single token on the table loses the game. Albert starts. Determine which of the two players has a winning strategy and describe such a strategy.
It is Albert who has a winning strategy. Let's analyze the positions:

Clearly, 1 is a winning position (since the player who must play has just won the game...), and 2 is a losing position because the player who must play is forced to leave a single token and loses the game. From this, we deduce that 3 and 4 are winning positions (the player can leave 2 tokens and thus give a losing position to the opponent). Therefore, 5 is a losing position because the player must then leave 3 or 4 tokens, giving a winning position to the opponent. This implies that 6, 7, 8, 9, and 10 are winning positions (the player can leave 5, which is losing), but 11 is a losing position (the player is forced to leave 6, 7, 8, 9, or 10, which are winning).

To avoid doing everything by hand, it is wise to take a broader view. For this, we observe that if $k$ is a losing position, then $k+1, k+2, \ldots, 2k$ are winning positions (the player can leave $k$, which we have just assumed to be losing), and $2k+1$ is a losing position (the player is forced to leave $k+1, k+2, \ldots, 2k-1$, or $2k$, which are winning). This allows us to determine the losing positions (and the winning positions) step by step, but more quickly... Thus, the losing positions are

$2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, \ldots$

Therefore, 1999 is a winning position, which concludes the problem.

## Remark.

More generally, using what we have just done, we can prove that the losing positions are the numbers of the form $3 \times 2^n - 1$, where $n \geq 0$ is an integer.