## Just Beatty It

[This is the 6th post in the current series about Wythoff's game: see posts #1, #2, #3, #4, and #5. Caveat lector: this post is a bit more difficult than usual. Let me know what you think in the comments!]

Our only remaining task from last week was to prove the mysterious Covering Theorem: we must show that there is exactly one dot in each row and column of the grid (we already covered the diagonal case). Since the rows and columns are symmetric, let’s focus on columns.

The columns really only care about the x-coordinates of the points, so let’s draw just these x-coordinates on the number-line. We’ve drawn $$\phi,2\phi,3\phi,\ldots$$ with small dots and $$\phi^2,2\phi^2,3\phi^2,\ldots$$ with large dots. We need to show that there’s exactly one dot between 1 and 2, precisely one dot between 2 and 3, just one between 3 and 4, and so on down the line. For terminology’s sake, break the number line into length-1 intervals [1,2], [2,3], [3,4], etc., so we must show that each interval has one and only one dot:

Multiples of $$\phi$$ (small blue dots) and of $$\phi^2$$ (large green dots) perfectly interleave the integers on the number line. This is proved below.

Why is this true? One explanation hinges on a nice geometric observation: Take any small dot s and large dot t on our number-line above, and cut segment st into two parts in the ratio $$1:\phi$$ (with s on the shorter side). Then the point where we cut is always an integer! For example, the upper-left segment in the diagram below has endpoints at $$s=2\cdot\phi$$ and $$t=1\cdot\phi^2$$, and its cutting point is the integer 3:

When a segment formed by a small and a large dot is cut into a $$1:\phi$$ ratio (closer to the small dot), the cutting point is always an integer. In fact, the segment between $$j\cdot \phi$$ and $$k\cdot \phi^2$$ is cut at the integer j+k.

In general, if s is the jth small dot—i.e., $$s=j\cdot\phi$$—and $$t=k\cdot\phi^2$$ is the kth large dot, then the cutting point between s and t is $$\frac{1}{\phi}\cdot s+\frac{1}{\phi^2}\cdot t = j+k$$ (Why?![1]). But more importantly, this observation shows that no interval has two or more dots: a small dot and a large dot can’t be in the same interval because they always have an integer between them![2]

So all we have to do now is prove that no interval is empty: for each integer n, some dot lies in the interval [n,n+1]. We will prove this by contradiction. What happens if no dot hits this interval? Then the sequence $$\phi,2\phi,3\phi,\ldots$$ jumps over the interval, i.e., for some j, the jth dot in the sequence is less than n but the (j+1)st is greater than n+1. Likewise, the sequence $$\phi^2,2\phi^2,3\phi^2,\ldots$$ jumps over the interval: its kth dot is less than n while its (k+1)st dot is greater than n+1:

Illustrating the hypothetical situation where interval [n, n+1] contains no dot. This is used in a proof by contradiction to show that the interval in fact cannot be empty.

By our observation above on segment $$s=j\phi$$ and $$t=k\phi^2$$, we find that the integer j+k is less than n, so $$j+k\le n-1$$. Similarly, $$j+k+2 > n+1$$, so $$j+k+2 \ge n+2$$. But together these inequalities say that $$n\le j+k\le n-1$$, which is clearly absurd! This is the contradiction we were hoping for, so the interval [n,n+1] is in fact not empty. This completes our proof of the Covering Theorem and the Wythoff formula!

It was a long journey, but we’ve finally seen exactly why the Wythoff losing positions are arranged as they are. Thank you for following me through this!

### A Few Words on the Column Covering Theorem

Using the floor function $$\lfloor x\rfloor$$ that rounds x down to the nearest integer, we can restate the Column Covering Theorem in perhaps a more natural context. The sequence of integers $$\lfloor\phi\rfloor = 1, \lfloor 2\phi\rfloor = 3, \lfloor 3\phi\rfloor = 4, \lfloor 4\phi\rfloor = 6, \ldots$$ is called the Beatty sequence for the number $$\phi$$, and similarly, $$\lfloor\phi^2\rfloor = 2, \lfloor 2\phi^2\rfloor = 5, \lfloor 3\phi^2\rfloor = 7, \lfloor 4\phi^2\rfloor = 8,\ldots$$ is the Beatty sequence for $$\phi^2$$. Today we proved that these two sequence are complementary, i.e., together they contain each positive integer exactly once. We seemed to use very specific properties of the numbers $$\phi$$ and $$\phi^2$$, but in fact, a much more general theorem is true:

Beatty’s Theorem: If $$\alpha$$ and $$\beta$$ are any positive irrational numbers with $$\frac{1}{\alpha}+\frac{1}{\beta}=1$$, then their Beatty sequences $$\lfloor\alpha\rfloor, \lfloor 2\alpha\rfloor, \lfloor 3\alpha\rfloor,\ldots$$ and $$\lfloor\beta\rfloor, \lfloor 2\beta\rfloor, \lfloor 3\beta\rfloor,\ldots$$ are complementary sequences.

Furthermore, our same argument—using $$\alpha$$ and $$\beta$$ instead of $$\phi$$ and $$\phi^2$$—can be used to prove the more general Beatty’s Theorem!

### Notes

1. Hint: use the identity $$\frac{1}{\phi}+\frac{1}{\phi^2}=1$$. []
2. To be thorough, we should also check that no interval has two small or two large dots. Why can’t this happen? []

## Putting the Why in Wythoff

Last week we drew dots at multiples of the vectors $$v=(\phi,\phi^2)$$ and $$w=(\phi^2,\phi)$$, and we colored grid-cells green or yellow according to whether they contain a dot or not. Our remaining task was to prove these three facts:

• Endgame condition: The cell (0,0) is green.
• Greens lose: From a green cell, there are no other green cells accessible with a single Wythoff’s game move.
• Yellows win: From any yellow cell, it is possible to move to a green cell with one Wythoff’s game move.

Our guess at the solution to Wythoff's game: multiples of vectors v and w (dotted) and their containing cells (dark green).

The “Endgame” condition is easy: the dot at $$0\cdot v = (0,0)$$ makes cell (0,0) green. One condition down, two to go!

The “Greens lose” condition asks us to show that no two green cells are in the same row, column, or (slope 1) diagonal—otherwise, you could get from one to the other with a Wythoff move. In fact, we will prove something stronger:

Covering Theorem: Every row, column, and diagonal contains exactly one green cell.

Pictorially, this says that each thick line in the diagrams below will hit one and only one green cell:

All columns (left), diagonals (right), and rows (not pictured) contain exactly one green cell. (Some of these green cells are beyond the image boundaries.) Because the green cell locations are symmetric through the line y=x, the diagram for the rows is redundant and therefore omitted.

It is not difficult to describe why each diagonal is covered, i.e. has exactly one green cell. In the diagram on the right, the central diagonal line has equation $$y-x=0$$; the one above it has equation $$y-x=1$$; the next is $$y-x=2$$; and so on. And because $$\phi^2-\phi=1$$, the vector v jumps from one diagonal line to the next at each step. Vector w similarly jumps from line to line in the other direction.

By contrast, I find the fact that each column is covered quite surprising. It says that the upper and lower branches of the “V” perfectly complement each other, each filling exactly the columns that the other skips! Before we prove this fact, let’s see why it helps us.

If we assume the covering theorem for now, we can finish the three conditions needed for our proof. We already saw that (0,0) is green, and the covering theorem certainly tells us that each row, column, and diagonal has at most one green cell, so the “Greens lose” condition holds. We just have to prove the “Yellows win” property: that you can always move to a green cell from any yellow cell. The idea is simple: if your yellow cell is above the “V”[1] then move down to the unique green cell in your column (which may be on either the upper or lower “V” branch). If you are below the “V”, move left to the green cell in your row. Finally, if you are inside the “V”, move diagonally. In this way, you can always move to a green cell with one Wythoff move.

All yellow cells can reach a green cell with one Wythoff move. Yellow cells above the "V" can move down to a green cell; yellow cells below the "V" can move left to a green cell; yellow cells inside the "V" can move diagonally to a green cell.

With this third and last property verified, we’re finally done with our proof! …except that we still need to prove the mysterious covering theorem. We’ll discuss this next week. Come back then for the exciting QED!

### Notes

1. i.e., its lower-left corner is above the line $$y=\phi\cdot x$$ []

## Wythoff’s Formula

Welcome back! I took a few-weeks’ blogging hiatus to focus on end-of-term craziness, but I am now resuming a regular(ish) weekly schedule throughout the summer. Let’s get back to Wythoff’s game!

Here’s a brief recap: In trying to solve for optimal play in Wythoff’s game, we saw how to algorithmically find the blue “losing positions”; we observed that these seemed to lie on two lines and, assuming this fact, we computed the lines’ slopes to be $$\phi$$ and $$1/\phi$$; and we saw how the Fibonacci numbers were hiding all over the place. But one question lingers: why lines? We’ll answer this today.

Two posts ago, we saw that if we take all of the (infinitely many) steps in the upper “V” branch and average them together, the result has slope $$\phi$$. In fact, with a little more work we can compute this “average step” exactly, not just its slope: it is the vector $$v=(\phi,\phi^2)$$.[1] Let’s compare these average steps, namely v, 2v, 3v, etc., with the actual ones:

Drawing a dot at each mutliple of the "average" step v reveals a perfect correspondence between dots and blue cells.

The dots and blue squares are perfectly matched! It seems that this may provide a precise way to easily locate all the blue cells in the upper “V” branch at once! And since the whole diagram is symmetric through the line $$y=x$$, the lower “V” branch should be governed by vector $$w=(\phi^2,\phi)$$ in the same way. Thus, a hypothesis forms:

Conjecture: The losing cells in Wythoff’s game are exactly those that contain an integer multiple of vector $$v=(\phi,\phi^2)$$ or vector $$w=(\phi^2,\phi)$$.

If we use the notation $$\lfloor x\rfloor$$ for the floor function that rounds x down to the nearest integer[2], then this conjecture says that the nth blue cells on the upper and lower “V” branches have coordinates $$(\lfloor n\cdot\phi\rfloor, \lfloor n\cdot\phi^2\rfloor)$$ and $$(\lfloor n\cdot\phi^2\rfloor, \lfloor n\cdot\phi\rfloor)$$ respectively. (When $$n=0$$, both formulas give (0,0).)

As we will see, this conjecture is indeed correct. How could we rigorously prove this fact?

To start, in a new grid, let’s color green all cells that fit our hypothesized formula, i.e., contain a multiple of v or w. Fill the rest of the cells with yellow. We now have two separate, a priori unrelated colorings of the grid: one with red/blue according to Wythoff’s game, and another with yellow/green according to vectors v and w.

Two colorings of Wythoff's grid that we conjecture are identical. Left: the losing positions (dark blue) found previously by an iterative, optimal-play strategy. Right: multiples of vectors v and w (dotted) and their containing cells (dark green).

Proving the conjecture amounts to showing that these colorings are the same. We’ll accomplish this by showing that the yellow/green coloring behaves just like the red/blue one:

• Endgame condition: The cell (0,0) is green.
• Yellows win: From any yellow cell, it is possible to move to a green cell with one Wythoff’s game move.
• Greens lose: From a green cell, there are no other green cells accessible with a single Wythoff’s game move.

We have already observed these three properties for the red/blue coloring, and we saw that they uniquely determined the red and blue cell positions. If we could show the yellow/green coloring follows the same pattern, we could conclude that the colorings are indeed identical. So we just need to check that our yellow/green formula satisfies these three conditions!

Now that we have set the stage to dig into the meat of this proof, it is time to bid farewell until next week. See you then!

### Notes

1. Indeed, since we know that a=(1,2) and b=(2,3) appear in proportion 1 to $$\phi$$, the average step is $$\frac{1}{1+\phi}a+\frac{\phi}{1+\phi}b = (\phi,\phi^2)$$. This can also be computed from the Fibonacci observations in the most recent post. []
2. For example, $$\lfloor 2.718\rfloor = 2$$, $$\lfloor 5\rfloor = 5$$, and $$\lfloor -3.14\rfloor = -4$$. []