Removing chips from the table

Question

Alice and Bob play the following game with $n\ge2016$ chips on the table.

• Alice and Bob move alternatingly. Alice makes the first move.
• In every move, the active player removes $k$ chips from the table, where either $k=1$, or $k$ is a multiple of $23$, or $k$ is a prime number.
• The player who takes the last chip wins the game.

Question: Which player is going to win this game? (As usual, we assume that Alice and Bob both use optimal strategies.)

Answer 1

From any multiple of 4 less than 92, any move leaves a number of chips that is not divisible by 4. Then, removing 1, 2, or 3 chips results in another multiple of 4. Therefore, any multiple of 4 less than 92 is a losing position, and all other numbers less than 92 are winning positions.

From any number greater than or equal to 92, it is possible to remove a multiple of 23 chips to leave a multiple of 4 less than 92 (including zero). Therefore, Alice wins.

Answer 2

On their turn, each player can remove 1, any prime number, or 23*n chips on their turn (for any integer value n).

Fundamentally, the goal of the game is to take the last chip.

The key thing to note is that amongst the numbers of chips we can remove are 1 (explicitly allowed), 2 (prime), and 3 (prime), but not 4.

This means that if a player starts their turn with 4 chips on the table, they have already lost the game (since their only legal moves are to remove 1, 2, or 3, and their opponent will respond by removing 3, 2, or 1, respectively, thus removing the last chip)

And this in turn means that if a player can, as their move, reduce the table to 4 chips, then they will win on their next move.

This logic also applies for 8; if a player can bring the count of chips to 8, then they will win in two more rounds of play, the first of which will bring the value to 4, and the second will bring the value to 0, through exactly this same process.

In the same way, it applies to 12, 16, etc. All the multiples of 4. The optimum strategy for this game, as it turns out, is very concerned with multiples of 4.

Whomever can get the number of chips to a multiple of 4 first, wins the game.

But there's one exception to this. If our opponent can somehow take the value from one multiple of 4 to a different multiple of 4, then they can take over the game. So! Since the first player (Alice) will use her first move to get the number of chips to a power of four, Bob wants to remove a multiple of 4 on his turn in order to gain control of the game (n.b.: (4x) - (4y) == 4(x-y). That is, subtracting any multiple of 4 from another multiple of four leaves you with a multiple of four as the result)

So as a reminder, Bob's options for number of chips to remove are: 1 (not a multiple of 4), any prime (not a multiple of 4, by definition, and 4 itself is not prime), or any multiple of 23.

As it happens, there are a whole bunch of multiples of 23 which are also multiples of 4. 23*4 == 92 is the smallest positive one. So to take back control of the game, all Bob has to do is to take 92 chips from the table, and now he can play the "stay on a multiple of 4" game that we describe above, and be guaranteed a win.

However, Alice (being the annoyingly perfect logician that she is), knows that this is Bob's only possible escape from this strategy. And so she'll block it with her first move, in which she'll remove (23*84==) 1932 chips, leaving only 84 on the table. From here, Bob can't use the magic "take 92 chips" move which would give him control control of the game, as there aren't that many chips available for him to take

No matter what move Bob makes, it will result in a non-multiple-of-four number of chips, and Alice can then remove 1, 2, or 3 chips to return the chips to a lower multiple of four. And eventually, win the game.