Nim Part 1

According to Wikipedia, “Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps.”[1] We are going to simplify the game slightly and only have one heap of objects with players removing up to a maximum number per turn. The winner of Nim is the person who removes the last object from the pile. The two players are Alice and Bob. Alice always starts. So let us get started with a simple example. Say you have a pile of 10 stones and each player can remove up to 2 stones, what could a game look like? Here we go:

Alice removes 1 stone, 9 stones remaining.

Bob removes 2 stones, 7 stones remaining.

Alice removes 1 stone, 6 stones remaining.

Bob removes 1 stone, 5 stones remaining.

Alice removes 2 stone, 3 stones remaining.

Bob removes 2 stones, 1 stone remaining.

Alice removes 1 stone, 0 stones remaining. Alice wins!

Nim

There you have it: a simple game of Nim with Alice as the winner. However, a perceptive individual might wonder, “Is there a pattern to this game? Is there a winning strategy?”

Rewinding a bit, what if Alice were to take the 4th last stone, leaving 3 stones in the pile? Then Bob could either take 1 or 2 stones. Using a diagram, we can see what happens.

Capture1

From the above flow chart, it is clear that no matter what action Bob makes, Alice can counter it and come out victorious. Therefore, as long as Alice is able to leave a pile of 3 stones for Bob, Alice will always win. Facing down a pile of 3 stones is bad news for Bob.

Rewinding another step, what if Bob was facing a pile of 6 stones?

Capture2

Again we see that from 6 stones, no matter what move Bob makes, Alice will be able to counter him and leave him with a pile of 3 stones. Further, we already know that leaving Bob with 3 stones assures her a victory. Poor Bob loses when he is facing down a pile of 6 stones as well. The same logic can be applied if Bob is staring at a pile of 9 stones.

Since the original pile starts with 10 stones, if Alice takes 1 stone to start the game off, leaving a pile of 9 stones, she will win 100% of the time. What do 3, 6 and 9 all have in common? They are all multiples of 3!

So there you have it: if you can leave your opponent with a pile of stones that is a multiple of 3 then you will win. Another way of thinking about this is that 3, 6 and 9 all have remainder 0 when divided by 3. The strategy employed by Alice is to remove enough stones each round so that she leaves Bob on a multiple of 3. As seen in the flow charts above, if Bob removes 1 stone, Alice should remove 2 stones. Similarly, if Bob removes 2 stones, Alice should remove 1 stone. And her victory is certain.

Advertisements

3 Comments

Filed under Uncategorized

3 responses to “Nim Part 1

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

  2. Pingback: Nim Part 3 | the Math behind the Magic

  3. Pingback: The game of NIM « Panda.Math.Games

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