## 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.

## 1-Pile Nim

Trivial – take all except 1.

## 2-Pile Nim

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