Nim Part 3

Mathematicians love to generalize ideas. In the previous posts (part 1 and 2) we considered the game of Nim with only 10 stones. What would happen if we had a different amount of stones to start?

What if we changed the setup and there were 9 stones in the pile? Alice would want to remove enough stones so that she could land on a 3, 6, or 9. However, this is impossible. Suddenly it seems as if the tables are turned. Whatever number of stones Alice removes, Bob will be able to counter it and land on the 6. Then after another round, Bob will land on the 3. Finally, Bob will win!

Clearly, Alice was doomed from the start. What is it about 9 that was so different from 10? 9 is a multiple of 3, so it already is a bad pile. Alice is starting on a multiple of 3, and since she still has to play her turn and remove some stones, she must leave the multiple of 3. Bob is then able to expertly land on the 6. Bob then navigates to the 3 and finally to the 0 for a win.

nim2

If we changed the number of stones to 11, it would be clear that Alice would win again (by removing 2 stones and leaving Bob with 9). Thus, if there are 9 stones Alice will lose (always assuming that Alice goes first), 10 stones Alice wins, 11 stones Alice wins.

The explanation is that Alice wants to finish her turn and leave a pile of stones that is a multiple of 3. In the case where the pile has 10 or 11 stones Alice can take 1 or 2 stones, respectively, and leave a pile of 9 stones. In the case where the pile has 9 stones there is no way for her to take enough stones to get to 6 and Bob will win.

What if there were 30 stones? Is 30 a multiple of 3? Yes. Alice will lose.

What if there were 406 stones? Is 406 a multiple of 3? No. Alice will win.

There could be any number of stones in the pile. All we have to do is ask the question, is it a multiple of 3? If it is, Alice will lose. If it is not, Alice will win. In modular arithmetic it would look like this (where n is the number of stones in the pile):

If n ≡ 0 (mod 3)                 then Alice will lose

If n ≢ 0 (mod 3)                then Alice will win

Modular arithmetic handy.

Advertisements

1 Comment

Filed under Uncategorized

One response to “Nim Part 3

  1. Pingback: Nim Part 4 | 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