[This is the *final* Wythoff’s game post. See the previous ones here: #1, #2, #3, #4, #5, #6. We’ll have a few shorter, 1- or 2-post topics starting next week.]

In our standard, base-10 number system, each position represents a specific power of 10: the number 275 in base 10 means that I have five 1s, seven 10s, and two 100s. Similarly, in the base-2 system, each position represents a different power of 2: 10011 in base 2 says I have a 1, a 2, and a 16, but no 4s or 8s.^{[1]} Instead of using powers of 10 or 2, what happens if we use Fibonacci numbers?

We can find the **Fibonacci numbers** by starting^{[2]} at \(a_1=1\) and \(a_2=2\) and then computing each term as the sum of the two previous ones, \(a_n=a_{n-1}+a_{n-2}\):

Let’s use *these* as our position values in our so-called **Fibonacci base**, using just the digits 0 and 1. For example, 1010011_{F} stands for \(a_7+a_5+a_2+a_1 = 21+8+2+1 = 32\).

Notice that \(a_2+a_1=a_3\), so we can write 32 instead as \(a_7+a_5+a_3\), meaning 32=1010100_{F}. In much the same way, any time we have a Fibonacci representation of a number, we can repeatedly use the identity \(a_n=a_{n-1}+a_{n-2}\) to ensure that we never use consecutive Fibonacci numbers:

Theorem (Zeckendorf): Every positive integer can be expressed in base Fibonacci with no adjacent 1s. Furthermore, this representation is unique.

The “base-Fibonacci representation” of a number usually refers to its **Zeckendorf representation** as in this theorem. There’s a simple *greedy* method to find a number’s Zeckendorf representation: use the largest Fibonacci number less than (or equal to) your number, and repeat on the remainder. For example, to represent 46 in this way, check that the largest Fibonacci number below 46 is \(a_8=34\), leaving 12 as the remainder. The largest Fibonacci number below (or equal to) 12 is \(a_5=8\), with a remainder of 4. Now we have to use \(a_3=3\), and finally we’re left with \(1=a_1\). So \(46=a_8+a_5+a_3+a_1=10010101_F\) is the Zeckendorf representation of 46.

But why discuss base Fibonacci now? What does this have to do with Wythoff’s game? Zeckendorf representations provide another simple way to characterize the losing positions in Wythoff’s game! Here’s a beautiful result:

Theorem: If \(a \le b\) are positive integers, then \((a,b)\) and \((b,a)\) are losing position in Wythoff’s game precisely when:

- The Zeckendorf representation of
aends in an even number of 0s, and- The Zeckendorf representation of
bis the same as that ofaexcept for one more 0 on the end.

For example, 11=10100_{F} ends in two 0s (two is even), and 18=101000_{F} has the same representation except for an extra 0 at the end, so (11,18) and (18,11) are Wythoff losing positions. Unlike the formula using multiples of \(\phi\) and \(\phi^2\) that we proved in the last few posts, this provides a method we could actually compute (without a calculator) on reasonably-sized grids when playing with friends (or enemies)! After all we’ve learned about Wythoff’s game, we finally have a way to win it!

### Further Reading

Our Wythoff’s game saga is now ending here on Three-Cornered Things, but here are a few recommended resources if you wish to further explore this rich topic on your own:

- Daniel Mathews. Mathellaneous: A Beautiful Sequence.
*Gazette of the Australian Mathematical Society*, 31(1):12–17, 2004. A survey of many fabulous properties of the Beatty sequence for \(\phi\). - Dr Ron Knott. The Golden String of 0s and 1s. A very thorough tour of the Fibonacci word, a.k.a., the “Rabbit Sequence” or our jump sequence.
- Beatty Sequences on Wikipedia.
- Robert Silber. Wythoff’s Nim and Fibonacci Representations.
*The Fibonacci Quarterly*, 15(1):85–88, 1977. A proof of the criterion stated in this post for computing losing positions with Zeckendorf representations.

### Notes

- If these concepts are unfamiliar, see this previous post on number bases. [↩]
- Careful: these indices are shifted from the other common convention that starts the Fibonacci numbers at \(F_1=1\) and \(F_2=1\), which is why I’m using
*a*s instead of*F*s. [↩]