[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, 1010011F 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=1010100F. 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 a ends in an even number of 0s, and
- The Zeckendorf representation of b is the same as that of a except for one more 0 on the end.
For example, 11=10100F ends in two 0s (two is even), and 18=101000F 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 as instead of Fs. [↩]
the proof has 2 sections :
i) the existence of Zeckendorf representation,
ii) the uniqueness of Zeckendorf representation.
proof of i)
suppose that the given number is n, then you can find the less or equal Fibonacci number to n, named F(j), so : F(j) <= n < F(j+1) (because the F(j) is the bigger Fibonacci number smaller than n). we write that : n = F(j) + a, we say a, as a reminder, while reminder is not zero, we continue. we claim that a is less than F(j-1), because if not, n would be bigger than F(j) + F(j-1), and we have F(j+1) = F(j)+F(j-1), this is contradiction with the main inequality, so the F(j-1) is absent in the representation of a, so there is no consecutive 1 in the representation, and we do so for reminder by induction and there will be no 1 adjacent to each other. This was the proof of existence.
proof of ii)
we do this by contradiction, suppose there is two set of Fibonacci numbers named T and S, such that the some of both are equal to n. We construct two new sets named S' and T' as below :
S' = S\T and T' = T\S (means delete the same numbers from each other)
so here S' and T' has no intersection, we will show that one of them is empty, imagine non of them is empty; suppose that F(s) is the biggest number of S' and F(t) is the biggest number of T', so by the definition of S' and T', we have that F(s) and F(t) are not equal. Without loss of generality we imagine that F(s) < F(t).
F(s-1) is absent is S' because of Zeckendorf representation defenition, so at most the F(s-2) will be in S', then the maximum sum of S' would be F(s) + F(s-2) + … which is less than F(s+1)
so sum of elements of S' is less than F(s+1) and by the way is at least F(t), this is contradiction, so on of the S' or T' is empty, because the sum of them are equal so the other should be empty too, so S and T are equal :), so this means the set in unique.
End,
Aww, no proof? I guess I’ll just have to try to prove it myself. =)