The Mathematics of Puzzles and Games

This webpage is a supplement to the Duke TIP class I taught at KU on November 8-9, 2008. It's under construction right now as I add material on the games we studied in the class, and some of their variations.

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 Bridge

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

• Wikipedia has a good article on Hex.
• PDF files with Hex gameboards: 6x6 boards 9x9 boards 11x11 boards
  (I found these at Larry Doolittle's website and converted them to PDF files.)

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

These games are often studied by economists in order to model real-world behavior.

Pawns

Start with a chessboard with 3 rows ("ranks")and n columns ("files"). Place white pawns on the bottom rank and black pawns on the top rank. White and Black take turns, with White moving first. The pawns move just as in chess; it can move to an empty square in front of it or capture a pawn of the opposite color diagonally in front of it. To win, you must either move a pawn to the opponent's back rank (which counts as two points) or reach a position where your opponent has no legal move (which counts as one point).

• Can you ever score two points (if your opponent knows what he or she is doing)?
• If both players play the best possible moves, who will win? This certainly depends on the value of n (the number of files in the game board). For what values of n can White ensure a win?