Table of Contents

Some More Notation

Let \(N_i\) be the set of positions from which the next player can force a win in at most \(i\) moves.

Subtraction game

\(S=\{1,2,3\}\). \(P_0 = \{0\} = P_1\). \(N_1 = \{1,2,3\} = N_2\).

\[N_{i+1} = \{x \in X \textrm{ s.t. } \exists \textrm{ a move from } x \textrm{ to } P_i\}\] \[P_{i+1} = \{x \in X \textrm{ s.t. } \textrm{ all moves from } x \textrm{ are to } N_i\}\] \[P_2 = \{0, 4\} = P_3\] \[N_3 = \{1,2,3,5,6,7\} = N_4\]

This gives us the following:

\[P := \bigcup_{i \geq 0} P_i\] \[N := \bigcup_{i \geq 0} N_i\]

and

\[X = P \cup N\]

###

Induction on \(B(x)\): max number of moves to end of game from \(x\).

Base case: \(B(X) = 0 \implies x \in P_0 \subseteq P\)

Inductive Hypothesis: \(\forall x \in X \textrm{ where } B(x) \leq n, x \in N_n \cup P_n\). Let \(y\) be such that \(B(y) \leq n + 1\).

Proof: Every move from \(y\) to \(z \in X\) will have \(B(x) \leq n\). There are two cases:

  • \(y\) goes to \(z \in N_n \implies y \in P_{n+1}\)
  • \(y\) goes to \(z \in P_n \implies y \in N_{n+1}\)

This shows that \(y \in P_{n+1} \cup N_{n+1}\)

Subtraction Game

\[S=\{1,3,4\}\]
x 0 1 2 3 4 5 6 7 8 9 10 11
\(F(x)\) \(\emptyset\) \(0\) \(1\) \(0, 2\) \(0, 1, 3\) \(1, 2, 4\) \(2, 3, 5\) \(3, 4, 6\) \(4, 5, 7\) \(5, 6, 8\) \(6, 7, 9\) \(7, 8, 10\)
\(P/N\) \(P\) \(N\) \(P\) \(N\) \(N\) \(N\) \(N\) \(P\) \(N\) \(P\) \(N\) \(N\)

Exercise: Show that \(x \in P \iff x \equiv 0, 2 \mod\ 7\)

Chomp

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

General Strategies (poison at bottom left):

  • \(n * n\): Remove the upper right square. By convention, it’s \((2,2)\).
  • \(2 * n\):

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?