Nim Part 4

In the previous post, we generalized the problem to any number of stones. How else could we generalize the problem? One option is to change the rules and take more stones! What would happen if you could remove 1, 2, or 3 stones? Suppose the pile only has 4 stones in it.

Capture3

Bob has his revenge! Alice (who goes first) is facing a pile of 4 stones and has no hope. She loses no matter what he does. This new game appears to centre on multiples of 4. If you are facing a multiple of 4 (4, 8, 12, 16) then you have no hope. On the other hand, if you are facing another number (3, 7, 13) you can take the correct amount of stones to leave your opponent with a multiple of 4 and secure your victory!

The reason that multiples of 4 are important is because 4 is one more than 3 (the maximum number of stones you can take). What if we changed the rules again and you could take 1, 2, 3, 4, 5, or 6 stones?

You would find that multiples of 7 are the key to victory.

In general, say you have a pile of “n” stones and you can remove at most “k” stones, what numbers will be the winning numbers and which player will win? We know that the multiples of “k + 1” will be important. In words, we would say that:

If n is a multiple of k+1                   then Alice will lose

If n is not a multiple of k+1           then Alice will win

In modular arithmetic, it would look like this:

If n ≡ 0 (mod k + 1)          then Alice will lose

If n ≢ 0 (mod k + 1)         then Alice will win and the strategy will be to remove “m” number of stones such that nm ≡ 0 (mod k + 1)

For example, what if you had 49 (n) stones and you could remove up to 9 (k) stones? Since 49 is not a multiple of 10 (k + 1), Alice will win! She should remove 9 stones to leave Bob facing 40 (a bad pile because it is a multiple of 10). Then she should remove however many stones she needs to keep him on a multiple of 10.

In conclusion, if you are in Alice’s position (Player 1) you need to calculate the multiples. If you are starting on a multiple, you will lose. If you are starting on any other number, you will win. So, next time your friends ask you to play a game of Nim, do a little modular arithmetic in your head first to see if it is really in your best interests to play.

Advertisements

1 Comment

Filed under Uncategorized

One response to “Nim Part 4

  1. Pingback: Nim Part 5 | the Math behind the Magic

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