A Golden Observation

Last week we saw that the best strategy for Wythoff’s game is to always move to one of the blue squares in the diagram below (if you can). We found the locations of the blue squares with an iterative algorithm that builds outward from (0,0), but we haven’t yet discovered the underlying pattern in how these blue cells are arranged. Let’s go pattern hunting!

As we noticed last week, the blue cells are arranged in a symmetric “V” shape, formed from two seemingly straight lines. What are the slopes of these lines? This is the question du jour.

Jumps in losing positions for Wythoff's game
Jumps between blue cells for Wythoff's game come in just two sizes: a=(1,2) and b=(2,3).

Looking more carefully, the upper branch of the “V” has only two types of “gaps”: consecutive blue cells are separated by either a “short” (1,2) step (a.k.a. a knight’s move) or a “long” (2,3) step. So, if we believe that this “V” branch is a perfect line, then that line’s slope should be somewhere between the slopes of these two steps, namely \(3/2=1.5\) and \(2/1=2\). Knowing more about how these steps are arranged will tell us more about the “V”.

Specifically, label these “short” and “long” steps as a and b respectively. What we care about is the ratio of bs to as. Why? For example, if there were an equal number of as and bs on average, then the slope of the line would be the same as the vector \(a+b=(3,5)\), i.e., the slope would be 5/3. If there were, say, two bs for each a in the long run, then the line would fall in the direction of \(a+2b=(5,8)\), with slope 8/5. Unfortunately, the ratio we seek is neither 1 nor 2; what is this magic number?

Let’s write down the sequence of jumps along our line. From the diagram above we see that it starts a b a b b a …, and using last week’s iterative algorithm, we can compute farther into this infinite sequence:

a b a b b a b a b b a b b a b a b b a b a b b a b b a b a b b a b b …

This sequence seems to be composed of “blocks” of (a b) and (a b b):

(a b)(a b b)(a b)(a b b)(a b b)(a b)(a b b)(a b)(a b b)(a b b)(a b)(a b b)(a b b)…

So for every a there are either one or two bs, meaning the ratio of bs to as is somewhere between 1 and 2. So the slope should be between 5/3 and 8/5. But what is it exactly? To answer this, we need to know how these “short” and “long” blocks are arranged.

Write A = (a b) and B = (a b b), so we can rewrite the sequence of blocks as

A B A B B A B A B B A B B …

Hold on; this sequence looks familiar. It’s exactly the same pattern as our original jump sequence! So it seems that the pattern of blocks is exactly the same as the pattern of the letters themselves! This is a “self-generating” sequence!

In particular, if the ratio of bs to as is some number r, then the ratio of (a b b) blocks to (a b) blocks is also r. But if we have one block of (a b) and r blocks of (a b b) then we have a total of \(1+2r\) bs and \(1+r\) as, so the ratio of bs to as is \(\frac{1+2r}{1+r}=r\). This simplifies to \(1+r=r^2\), and the solution is the shiny number \(r=\frac{1+\sqrt{5}}{2}\), known as the golden ratio and denoted \(\phi\) (Greek letter phi).

Now we know that our purported line should be in the direction of \(a+b\cdot\phi = (1+2\phi,2+3\phi)\), so the slope is \((2+3\phi)/(1+2\phi)=\phi\). And since our “V” shape is symmetric, the other line should have slope \(1/\phi = \frac{\sqrt{5}-1}{2}\). Done and done!

Well, yes and no. We found the slopes of the lines in the “V”, but why do they form lines at all? And what does all this have to do with the Fibonacci numbers?

6 thoughts on “A Golden Observation

  1. There is a solitaire-game which also leads to the Lower Wythoff Sequence. n piles of chips are standing in a row from left to right showing the amounts of chips 1, 2, 3, 4, …, n. Take always the leftmost pile an put its chips one by one and pile by pile on the piles right of it.
    Example startig with five piles 1 2 3 4 5
    after the first move 3 3 4 5
    after the second move 4 5 6
    If there is no more pile to put a chip on, build one-chip-piles:
    after the third move 6 7 1 1
    Keep on until the starting-position of the piles is mirrored 5 4 3 2 1
    and count the moves. You will count 8 moves and 8 is the fifth number in the Lower Wythoff Sequence.

        1. Dear Zachary,
          do you know which sequence I am writing about? I doubt since you didn’t notice the missing line and you didn’realize, that I wrote about the Lower Wythoff Sequence.
          Regards Roland

          1. Hi Roland,
            I think your original post was very clear: the number of moves in this n-pile solitaire game is the nth term of the Lower Wythoff Sequence. This is a lovely fact, and one I have not seen before, so thank you for sharing it! Where did you learn it? And do know a proof?

          2. Dear Zachary,
            thank you for your answer. As I can see you understood what I meant. This “lovely fact” i discovered on my own and I prooved it. The proof is published 2013 in german language: Der Goldene Schnitt in Türmen aus Spielsteinen, in Mathematische Semesterberichte, vol. 60, pages 51 – 66. I can translate my proof into a funny german colored english, if you want me to do so.
            regards Roland

Leave a Reply

Your email address will not be published. Required fields are marked *