A Game of Stones

A PuzzleCritic Original:

There are 999 stones in a pile. Amisi and Boaz take it in turns removing either 3 or 5 stones from the pile, with Amisi going first, until no more moves are possible. The last player to make a move wins. Which player can guarantee victory?

Okay, 999 is a big number. I don’t really want to investigate what happens by playing this game from the start. So let’s see what happens near the end of the game.

It is clear that, if after your turn, there are 0, 1 or 2 stones remaining, then you have won, since your opponent cannot move. If you leave 3, 4 or 5 stones, your opponent can remove 3 stones and leave 0, 1 or 2 stones, so they will win. Continuing in this fashion we can build up a list of good numbers (that we want to leave after our turn) and bad numbers (that we don’t want to leave after our turn).

0 – good

1 – good

2 – good

3 – bad

4 – bad

5 – bad

6 – bad (opponent can move to 2)

7 – bad (opponent can move to 2)

8 – good (opponent cannot move to a good number)

9 – good

10 – good

11 – bad (opponent can move to a good number, 8)

12 – bad

and so on…

 

After a while, a pattern emerges; it looks like a number is good precisely if it is of the form 8n, 8n+1 or 8n+2, where n is a whole number. Let’s prove this claim:

Certainly 0, 1 and 2 are good. If we subtract 3 from 8n, 8n+1 and 8n+2 we obtain 8n-3, 8n-2 and 8n-1 respectively, none of which are of the desired form. Similarly, subtracting 5 from each option yields 8n-5, 8n-4 and 8n-3, and again none of these are in the required form.

However, from any number of the form 8n+3, 8n+4, 8n+5, 8n+6 or 8n+7, it is possible to subtract 3 or 5 to obtain a number of the desired form: just subtract 3, 3, 3, 5 and 5 respectively from each.

In this way we see that, once a player leaves a number of stones of the form 8n, 8n+1 or 8n+2, their opponent is forced to leave a number of a different form, and then the first player can always reduce the pile of stones to a number of the desired form again. This player may control the game until the very end, whereupon his opponent cannot moves and loses.

Back to the original problem; the game begins with 999 stones. This is 7 more than a multiple of 8, that is, a bad number, and so it is Amisi who can guarantee the win. Her first move should be to reduce the pile to 994 stones, and then she can control the game as discussed above. Poor Boaz – no matter what he tries, there is little he can do to escape defeat. He can only hope Amisi makes a mistake…

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s