Monthly Archives: July 2012

Perplexing Paperclips

[I have spent the last few weeks worth of expository writing preparing the content (linked to) in this post, hence the longer-than-usual wait. Enjoy!]

Here’s a rather complicated collection of 54 loops:

Complicated collection of 54 loops

No two loops link through each other, and yet, these loops really don’t want to come apart. How hard is it to separate them? Well, suppose they were made of thin, bendable string, and we could move and (un)tangle them as much as we wanted as long as we kept the strings intact. Could we separate them? Absolutely not!

What if we allowed ourselves to cross strands through each other—real string can’t do this, of course. Then we could certainly get the loops apart, but how many such crossings would we need to use? As it turns out, we would need at least 108 strand crossings! This is a good first approximation of how much these loops don’t want to separate.

If the strands had open ends, then there would be no such knot-theoretic obstructions to building this shape. So we could, for example, make it with paperclips! (This is not easy…)

Pair o' Boxes Sculpture
The Pair o’ Boxes sculpture, made from 162 paperclips.

I call this Pair o’ Boxes, and it is one of seven new sculptures that I have recently uploaded to my Mathematical Sculpture page. More of these sculptures are shown below, and each has a detailed mathematical description (and larger pictures) at my sculpture page. Go check them out! The Pair o’ Boxes page in particular explains much more about the knot theory of the above structure, including a proof that 108 crossings are necessary to fully separate the strands.

Sculptures by Zachary Abel

Sorry for the shameless advertising; we now return to our regularly-scheduled posting.

Fibonacci-Based Arithmetic

[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}\):

1, 2, 3, 5, 8, 13, 21, 34, 55, …

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:


Notes

  1. If these concepts are unfamiliar, see this previous post on number bases. []
  2. 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. []