Jim and Nim

I presented my talk "Jim and Nim" yesterday at the Bard Math Seminar, and managed to fill the house.


My introduction actually extended over two days, as I visited math and CS classes on Wednesday and Thursday and personally invited students to my talk. This was really fun, and I got to meet some of Bard's amazing undergraduates. I teased them with the Magic Birthday Trick:

Have you seen this?

1. Identify the boxes that contain the day of the month that you were born. (For example, I was born on the 18th, and the number 18 appears only in the two boxes on the right.)
2. Add up the numbers in the top left of each box that includes your birthdate. (For me, that's 2 + 16.)
3. The sum is mathemagically your birthdate.
4. Share in the amazement!

Here's a picture that I used to explain why this trick works. I'll leave it to you to puzzle it out!

Another teaser I shared is the game I call 21-Nim. Start with 21, and on your turn you subtract 1, 2 or 3. The first person to reach 0 is the winner.  (My MAT student Kristen used this at our Pi Day Celebration for the students at 345 Brook Avenue in the Bronx.) What's interesting here is the set of losing numbers, and I challenged the Bard students to find them. In a losing position, the next player will lose, if her opponent plays correctly. Can you find the losing positions?

We didn't play 21-Nim during my talk, but we did play the classic game of Nim, with Teddy Bears:

Here's a picture of me, getting ready to hand out the teddy bears.

(This amazing photo is by Rusty, who was visiting Bard with his son Kyle the day of my talk.)

The Game of Nim

This is the real game of Nim, whose winning strategy was first described and proved in a math research paper published in 1901. The game starts with several piles of counters. Players alternate moves: on your turn, select a pile and remove at least one counter from that pile. You win if you take the last counter from the last pile. That is, the last player with a legal move wins. If you know the set of losing positions, then you know the winning strategy! 

Strategy

I had the participants play a few games of Nim, just to get the feel of the game and to start identifying the losing and winning positions. The amazing thing about impartial combinatorial games is that in each game position (with a finiteness condition) there must either be a winning strategy for you, or your opponent has a winning strategy. I call these two possibilities Winning and Losing positions (the standard notation from Winning Ways is N and P positions), which brings up a natural opportunity to use quantifiers:

• If you are in a Losing position, then EVERY move you make leads to a Winning position for your opponent.
• If you are in a Winning position, then there EXISTS a move that leaves your opponent in a Losing position.

I represented this in the following diagram:

Jim

Did I mention that I invented a Nim-type game that I call "Japheth's Nim", or Jim for short? One day in February 2011, I was running around Prospect Park in Brooklyn and thinking about how to motivate the strategy for Nim. Halfway around the park, I realized that a visual representation of the binary number strategy could be described independently of its connection to binary numbers and exclusive OR. I used the rest of my run to figure out just how to describe a Nim move visually in binary, which resulted in the game of Jim.

A Jim game starts with  several rows of red and yellow tokens. Players alternate moves: select a row, and change one or more tokens (yellow to red or red to yellow). The first token to be changed (from the left) must be yellow (but does not need to be the leftmost yellow token). The last player with a legal move wins. Equivalently, if you only see red tokens, then you’ve just lost! 

Here's a 3-row Jim game:

Can you explain why this is a Losing position?
One of the most exciting parts of the talk was at the end, when I revealed the connection between Jim and Nim with this slide:

Well, you might have had to be at my talk for this to make sense. Please leave a comment below to describe how Nim and Jim are related!