Backward induction and games

Idea: Start from the end

Label each position winning or losing for the player to move, from size $0$ upward.

• No moves left: losing, when the last item wins
• Winning: some move leads to a losing position
• Losing: every move leads to a winning position

Formula: Take-away games

$n\mathrm{mod}(k+1)=0$

With moves of 1 to k, the losing sizes are the multiples of k + 1; answer a move a with k + 1 − a.

Example: 21 matches

$21$ matches; each turn take $1$, $2$ or $3$; whoever takes the last wins. Go first? How many do you take?

1. Losing sizes are multiples of $4$; answer each $a$ with $4-a$
2. $21=5\times 4+1$, so go first
3. Leave $21-1=20$: take $1$

Common mistake: Misreading who wins

Using the same table when taking the last item loses. The losing sizes shift.

Instead Then leave $1$ more than a multiple of $k+1$, not a multiple. Read the winning rule twice.

Idea: Unusual move sets

The table works for any set of moves, even where no neat formula exists.

• Moves $1$, $3$, $4$: losing sizes $0$, $2$, $7$, $9$, $14$, $16$
• Remainder $0$ or $2$ on division by $7$, as $16=2\times 7+2$
• Find the period by filling the table, never by guessing

Quick check: Count the losing sizes

With moves of $1$, $3$ or $4$, how many pile sizes from $1$ to $30$ are losing for the player to move?

Formula: Nim: the binary sum

$a\oplus b\oplus c=0$

Add heap sizes in binary without carrying; the position is losing exactly when that sum is 0.

Example: Heaps of 3, 4 and 5

Nim with heaps $3$, $4$, $5$: take any number from one heap; the last item wins. How many do you take?

1. Binary $011$, $100$, $101$: the sum is $010$
2. Flip the middle bit of $3$: $001$, which is $1$
3. Take $3-1=2$ from the first heap

Idea: Say it in the room

State the losing positions first, then the move that reaches one.

• Take-away games: give the period and the reply rule
• Nim: say the binary sums column by column
• That column step is where slips happen