504 Combinatorial games
17.1.2 Subtraction of square numbers
Two players alternately subtract a positive square number. We calculate
the Sprague-Grundy sequence.
g(0) = 0
1 →0=⇒ g(1) = 1
g(2) = 0
3 →2=⇒ g(3) = 1
4 → 3 ,0=⇒ g(4) = 2
5 → 4 ,1=⇒ g(5) = 0
6 → 5 ,2=⇒ g(6) = 1
7 → 6 ,3=⇒ g(7) = 0
8 → 7 ,4=⇒ g(8) = 1
9 → 8 , 5 ,0=⇒ g(9) = 2
10 → 9 , 6 ,1=⇒ g(10) = 0
The values ofn≤ 1000 for whichg(n)=0are as follows:^1
Suppose we start with 74. Player A can subtract 64 to get 10, which
has value 0. This means no matter how B moves, A can always win.
This is clear if B moves to 9 or 1. But if B moves to 6, then A can move
to 5 which again has value 0, since now B can only move to 4 or 1.
Exercise
How would you win if the starting number is 200? or 500?
(^1) [Smith, p.68] incorrectly asserts that this sequence is periodic, with period 5.