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?

- 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.)
- Add up the numbers in the top left of each box that includes your birthdate. (For me, that's 2 + 16.)
- The sum is mathemagically your birthdate.
- Share in the amazement!

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 ﬁrst 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 ﬁrst 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!

## 3 comments:

Great presentation Japheth! Math IS fun and makes sense! :)

If I'm understanding the rules of Jim right, then they are actually isomorphic games, yes?

@ben - That's right, Jim is the binary representation of Nim. Each Jim row, when read in binary (yellow = 1, red = 0) is the number of teddy bears in the corresponding NIm pile.

The Jim strategy is easy (easier?) to understand - it's just a parity argument on the number of yellow chips in each column. I decided that understanding that strategy first, before linking Nim to its binary representation, was the way to go.

This still begs the question - why does Nim have this binary strategy? So, while I don't feel like I've shed much light on this question, I'm happy with the sequencing of explaining Nim strategy.

Post a Comment