Rubanov I.S.

There are $n$ matches on the table ($n>1$). Two players take them off the table in turns. On the first move, a player can take any number of matches from 1 to $n-1$, and then each time no more matches can be taken than the partner took on the previous move. The one who takes the last match wins. Find all $n$ for which the first player can ensure a win.
If $n$ is odd, the first player wins by taking one matchstick on the first move: from then on, both players are forced to take one matchstick at a time, and the last move will be the first player's.

If $n$ is even, the player who first takes an odd number of matchsticks loses, as they leave an odd number of matchsticks for their opponent on their turn. Therefore, to maintain a chance of winning, players must take an even number of matchsticks each turn. This means that we can mentally pair the matchsticks and consider that players take a certain number of pairs each turn. In this case, the following scenarios are possible.

1) $n=2$. Then the first player loses because they cannot take two matchsticks at once.
2) $n=4 m+2$. Then the first player will win by taking one pair on the first move.
3) $n=4 m$, that is, the number of pairs is even. To maintain a chance of winning, players must take an even number of pairs each turn. But then we can combine pairs into fours and consider that a certain number of fours are taken each turn. Conducting the same reasoning for fours as for pairs, we get that at $n=4$ the first player loses, at $n=8 m+4$ - wins, and at $n=8 m$ we need to transition to eights. Repeating these considerations further, we get that at $n=2,4,8,16, \ldots$ the first player loses, and at other $n$ - wins.

## Answer

$n \neq 2^{k}(k \in \mathbf{N})$.

Send a comment