Some More Notation

Let be the set of positions from which the next player can force a win in at most moves.


Subtraction game

. . .

This gives us the following:

and

###

Induction on : max number of moves to end of game from .

Base case:

Inductive Hypothesis: . Let be such that .

Proof: Every move from to will have . There are two cases:

  • goes to
  • goes to

This shows that


Subtraction Game

x 0 1 2 3 4 5 6 7 8 9 10 11

Exercise: Show that

Chomp

Exercise: Try to beat computer at Chomp. It’s hosted online by Ferguson.

General Strategies (poison at bottom left):

  • : Remove the upper right square. By convention, it’s .
  • :

See: 3-row chomp.


Nim

1-Pile Nim

Trivial – take all except 1.

2-Pile Nim

Take from larger pile to match other pile. This reduces to Tweedledum-Tweedledee.

3-Pile?