Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

share|improve this question
5  
Alice and Bob plays alot. They should also study sometimes...:p – manshu Jan 10 at 18:36
1  
@manshu, Now I'm imagine college students majoring in game theory complaining about homework. – user1717828 Jan 10 at 21:56
2  
Alice and Bob have been working hard on cryptography problems. Let them have a little fun. – CandiedOrange Jan 10 at 22:41
1  
@CandiedOrange So sad they will fail in their test tomorrow. – manshu Jan 10 at 22:55
up vote 23 down vote accepted

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.

share|improve this answer
1  
How is a multiple of 4 relevant? Also, how does Alice keep Bob from getting to a multiple of 4? – JonTheMon Jan 10 at 21:17
1  
@JonTheMon 4 is relevant because it is the smallest number of chips that is not possible to remove at once. Alice prevents Bob from getting to a multiple of 4 by always leaving a multiple of 4 less than 92 herself. It is not possible to move from such a position to another multiple of 4. – f'' Jan 10 at 21:49

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.

share|improve this answer
3  
This is really just a restatement of @f"'s answer, but trying to make the logic more explicit, and explaining why certain classes of move aren't ever helpful. – Trevor Powell Jan 11 at 9:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.