# Note 4 - A Look at Subtraction Games

## Table of Contents

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