Understanding the nimbers behind Wythoff's Game

This is just a sketch of some notes right now--don't read it--it is not worth your time yet.

What is Wythoff's Game?

This game is a version of Nim (you can play the original Nim here), which I will flesh out in the next update. In 1907, Wythoff gave a proof concerning "safe combinations," which are the conditions you would want to move to if you play the game, because they guarantee a win as long as you don't make any mistakes during the rest of the game (easier said than done for me). The original and pretty simple proof--the thing I am trying to understand. There's a copy of only the paper here, but the whole context--Dutch, English, French and German papers in one volume, as well as the range of topics, is interesting.

Describe the two-piles vs. movements of a1-seeking-Queen on chessboard interpretations, etc.

Rules

If the piles of tokens/queen's position are represented by the tuple (x,y), the allowable moves are:

1. Take from one pile/Leftward or downward move: (x,y) + (-n, 0) or (x,y) + (0,-n) for any positive integern
2. Take from both piles/Diagonal move: (x,y) + (-n, -n) for any natual number n

Observations

• (0,0) is the winning condition and by definition a safe combination
• There must be a winner, so there can't be safe combinations on two successive turns.
• There's no number in common (either x or y) among tuples in the set of safe combinations (application of the no-successive safe combinations observation \& rules 1 and 2; rule 1 says you can't have a difference of (0, n) between successive safe positions, and any number of (0, n) moves can be consolidated into a single move, so, even if it were the case that 6 successive moves of (0, -w), for different ws, they can be treated as one move. Rule 2 rules out having both numbers in common.
• If (x, y) is a safe position and y = x + d for some positive integerd (or x = y + d), then there is no other safe position (x', y') where x and y differ by d. This is the same idea as above--given two distinct safe combinations where y-x = d, you could get to the smaller of the two (i.e. the one with smaller Manhattan distance from the origin) from the larger one in a single move using Rule 2.

Steps for backwards recursion of safe combinations, given known safe combination (x0,y0)

• Gray out vertical lines: Exclude all grid cells having x = x0 or having x = y0
• Gray out horizontal lines: Exclude all grid cells having y = x0 or having y = y0
• Gray out diagonal lines from (x0, y0): Exclude all grid cells having (x = x0 + k, y = y0 + k) for all natural numbers k

Netlogo demonstration

todo: think about patterns for the gray vertical stripes above the diagonal during the recursion--what's up with those? This also looks like the "particles" in the majority cellular automaton of Mitchell and Crutchfield (?)--what's going on there?

The Claim

Wythoff's core claim is that all safe combinations can be found by substituting all positive integers k into Equation 1: x = ⌊½k(1 + √5)⌋, y = ⌊½k(3 + √5)⌋ (where ⌊z⌋ is floor(z), a/k/a the largest integer that is smaller than z).

Skeleton of the proof

• Given any positive integer k, show that Equation 1 works and that there is no other positive integer that produces the same safe combination. The proof begins with k and searches for multiples of the starting tuple calculated using Eq. 1, finding that no distinct tuple (x', y') that satisfies the Rules and Observations has a difference of k.

Steps (TODO: make this clearer)

1. Choose some positive integer n
2. Find A and B, defined as the smallest differences between some multiple of (1 + √5) and (3 + √5), respectively, and n
3. Derive various properties of A,B, ultimately finding Equation 2: ⌊½A(-1 + √5)⌋ + ⌊½B(3 - √5) = 1; Eq 2. is only satisfied for the inadmissible values A = B = 1
4. Eq. 2 implies that either A < 1 and B > 1 or that A > 1 and B < 1, exclusively, and in the former case that n = ⌊½p(1 + √5)⌋ for some integer p, while in the latter n = ⌊½q(3 + √5)⌋ for some integer q
5. All together, this implies that for any n, there is only one pair p, q such that p + q - n = 1 and both Eq. 1 and Eq. 2 hold
6. Since p and q determine the components of the safe combination and are unique, Wythoff's claim is justified.

Why (1 + √5) and (3 + √5)?

• Their difference is 2
• for v = 1 or 3, |5 - v^2| = 4
• this lets the double-halving transformation that Wythoff uses return a unit difference

Other Wythoff Games

Wythoff moves on from finding all positive integer differences between x and y to finding systems where x and y differ by distinct multiples of some positive integera. What happens when such games are based on as that are not relatively prime?

Pell's Equation Properties

A subset of the other Wythoff games (that includes the game involved in the claim) have safe combinations x = ⌊½(-a + 2 + √(a^2+ 4))⌋, y = ⌊½(a + 2 + √(a^2+ 4))⌋. The game discussed so far has a = 1.

Taking the norm of such numbers to be z*z, where z is a conjugate (i.e.x = ⌊½((-a + 2) - √(a^2+ 4))⌋), the (absolute value of the) norm is a. The difference of a pair of these numbers (y - x, where y > x), is also a. This forces the uniqueness of x - y differences for distinct safe combinations (as in steps 5 and 6 above). Note also that all of these fall on lines which will have slopes that are some integer times the golden ratio. I think that when I am saying that the norm and difference of these numbers are the same, it is in some way equivalent to the golden ratio property where, numbers c,d, with d > c, satisfy the ratio when (c+d)/c = d/c.

How can these properties come out of movements in the game?