The Mathematics of Puzzles and Games

Here are the course materials for my Duke TIP Scholars Weekend "The Mathematics of Puzzles and Games", which I've taught at KU on November 8-9, 2008 and March 6-7, 2010.

Nim

To play this game, you need a set of counters that are separated into piles. Two players take turns in alternation. On his or her turn, a player may remove any number of counters from a single pile. The winner is the player who takes the last counter.

• A mathematical fact called the Sprague-Grundy Theorem says that, in a certain sense, many other games are equivalent to Nim.
• In the "misère" form of Nim, the last player loses instead of winning. How does the strategy differ in this version of the game?

One-Suit Whist

To play this game, shuffle a one-suit deck of 2n cards and deal n cards to each player. Both players lay their cards face up on the table. At each turn ("trick"), first one player, then the other, plays a card. Whoever plays the higher card wins the trick and plays first to the next trick. The object is to take as many tricks as possible.

• What is the weakest hand that can take 1, 2, 3, ... tricks?
• For some hands, it matters who goes first; for others, it doesn't. How can you tell?
• Is it ever an advantage to go first? (The answer is no, but this is surprisingly difficult to prove mathematically.)
• Should you always win the trick when possible?
• This is a simplification of the wonderful card game of bridge (which involves all four suits and bidding).
• What if you add more suits? For example, deal each player three hearts, two spades and one club, and require players to follow suit (i.e., if the first player to a trick plays a spade, then the second player must also play a spade). Can you construct a three-suit deal where it is an advantage to go first?

The 15-Puzzle

Hex

Handout on Rules and Strategy [PDF]

Blank gameboards you can print out: 6x6 | 9x9 | 11x11
(I found these at Larry Doolittle's website and converted them to PDF files.)

Matrix Games (Prisoner's Dilemma, Chicken, etc.)

Handout on Rules and Strategy [PDF]

Games with Colored Hats

Handout on Rules and Strategy [PDF]

Evil Professor Nitram Puzzles

Handout with the puzzles [PDF]