# Note 4 - A Look at Subtraction Games

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