Nim Part 6

Just when I thought Nim was done, I remembered that I had only generalized to 3 players! What about 4 or 5 or more players? The details of my analysis get very technical. Therefore, instead of boring you with a wall of text about the intricacies of programming an algorithm to optimize a strategy for playing Nim with p players, I will opt instead to show you some interesting pictures.

Below is the strategy graph for 4 players. Once there are 10 stones (yellow), the pattern becomes evident and contains 6 nodes. The yellow, pink, green, light purple, teal, and lavender groups all have 6 nodes in them. Further, each group has the same structure.

nim4

Below is the strategy graph for 5 players. Here the pattern starts at 13 stones and contains 8 nodes. The yellow, lavender, teal, and light green groups all have 8 nodes in them.

nim5

Finally, here is the graph for 6 players. The pattern does not start until 23 stones and contains 9 nodes. Again, we ignore the purple, red, and green nodes. Starting with the deep blue nodes, and continuing with the pink and brown nodes, we can see a similar pattern with 9 nodes in each.

nim6

The strategies for more players follow very similar graphs. One important characteristic of each picture is the number of nodes in the repetition (9 in the picture above). Below is a table of these results for many more players:

Number of Players Number of nodes in repetition
2 3
3 5
4 6
5 8
6 9
7 11
8 12
9 14
10 15
11 16

The number of nodes is increases by 1 or 2 each time. This pattern is easy to generalize:

n = \lfloor \frac{3p}{2} \rfloor

Where p is the number of players, n is the number of nodes, and the fancy brackets (called the floor function) tell you to round down if you get a decimal. Thus, if there were 45 people playing Nim, the pattern would repeat every:

\lfloor \frac{3 \times 45}{2} \rfloor = \lfloor 67.5 \rfloor = 67 nodes

So where does this leave us? After mining the depths of Nim we have found that the simple sequence:

3, 5, 6, 8, 9, 11, 12, 14, 15, 16, …

created by adding 1, then adding 2, is intimately related to determining the optimal strategy for any number of players in the game of Nim. This connectedness between ideas lies at the heart of mathematics. The connections between these ideas are beautiful.

Advertisements

Leave a comment

Filed under Uncategorized

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