From rope-cutting to Golomb rulers, via magic

I’ve been learning a bit about Golomb rulers recently: a ruler which has so few markings that if you can use it to measure some whole number length, then you can only measure it in one way. I first read about them on the monthly AMS feature column, about their applications inside and outside of maths (to codes, radar, sonar and suchlike), and then watched an excellent TED talk using one particularly useful two-dimensional generalisation (a Costas array) to create a piece of piano music so dissonant that no time-step or jump in pitch between any pair of notes (not necessarily adjacent) is the same.

A perfect Golomb ruler with markings at 0,1,4 and 6, can measure any whole length from 1 to 6, but each in only one way.

I started to wonder about whether Golomb rulers had anything to do with a real-life problem I’ve previously written about, that someone who owned a barge had wanted answered. He asked about how to cut ropes into different lengths so you can knot them together in combinations and get a large variety of new lengths. I had decided the link was merely thematic, until someone else asked me whether they were the same, and prompted me to have a closer look. It turns out the two are somewhat linked, and what’s more, the link can be viewed as a silly little piece of mathemagic!

The Rope

As I want to start using ‘pure’ mathematics, I’ll explicitly reformulate and simplify the original vaguely-defined rope-cutting problem. A bargeman has a length of rope ( metres long) and wants to cut it up into several pieces which are each a whole number of metres in length, so he can knot the pieces together (with eye-splices) into various different lengths. He only wants to use at most one knot.

In my previous post about the problem, I observed that if he can make a certain length in two different ways then a potential combination is wasted. Inspired by this insight, (the now fictional) bargeman over-zealously insists that each possible rope-length, knotted or unknotted, can only be made in at most one way. The second outrageously pointless constraint is that a ropes tied with a theoretical second copy of itself, doesn’t cause a repetition.

Rephrasing this in some light mathematical notation, he wants us to find some whole numbers such that , and where if and only if . I’ve set so that we can notationally say that every combination is knotted: we pretend a single rope is knotted with a rope of zero length. We can also easily reorder the numbers so that .

For this article, let’s call any cut-up rope lengths that fit the theoretical bargeman’s strenuous conditions, “a strict Bargeman’s rope”. The lengths of such rope are also more formally known as a Sidon set (or Sidon sequence). And now the main point of this post: every strict Bargeman’s rope or Sidon set is also a Golomb ruler, and visa-versa!

The Trick

Here’s the very literal trick that links the two. The reasoning behind it will have to wait until the end of the article.

The set-up: Cut or neatly tear a long length of paper in half, so you have two long strips of paper of equal length. Colour one of them in to distinguish it from the other. Claim this is a magical colour that bends the audience’s choices to your will, or some such nonsense.

Audience participation: Now explain to an audience volunteer that you are going to cut the blank strip across the short width, to make two shorter strips (if you’re not using scissors, get a clean line by folding back and forth, before tearing). Then tell them you are giving them the magical coloured strip and ask them to do the same as you did (but ask them not to cut it in the quite the same position, or this simple trick will be even less impressive!).

The pay-off: Place the audience member’s short, coloured piece on top of your longer, plain piece, lining up the ends precisely. Now, in the same way, cover up the end section of the longer coloured piece with your shorter plain piece. Line up the two lengths of the bottom paper that aren’t covered, and you will surely be amazed to discover that they are exactly the same length!

Try it yourself, if you don’t believe me. Or read on.

The Ruler

A Golomb ruler has so few markings that any whole number length we can measure, can be found in only one way. This is the main feature of a Golomb ruler: you can’t always find every whole number length using a Golumb ruler. If you can, it’s known as a perfect Golumb ruler, and the “1,4,6 ruler” pictured above is the longest perfect Golumb ruler that exists.

Here’s a pair of imperfect rulers:

“We wants it, we needs it. Must have the preciousss Golomb rulers.”

All together now

The link between the strict Bargeman’s ropes (or Sidon set) and the Golumb rulers is incredibly simple. Every set of strict Bargeman’s ropes gives a Golumb ruler, and every Golumb ruler gives a set of strict Bargeman’s ropes.  Just choose the same numbers! Amazingly, the link between the two went unnoticed for about forty years, until this 2002 thesis by Apostolos Dimitromanolakis. It’s heartening to know that there is still simple mathematics to discover!

In mathematical parlance, we call this strong two-way link an isomorphism. It means, mathematically, they are completely identical, but it is two different ways of looking at the same (mathematical) object.

Mathematicians aren’t convinced by coincidences however: we need proof. This is where the magic trick comes in. If we had a set of strict Bargeman’s ropes (of lengths ) and we convert it to a ruler using the same numbers, then we can measure a length between the and markings, where , that is, a length of . Now let’s check whether this ruler is Golumb or not.

If it wasn’t a Golumb ruler, then there be some length we could measure with the ruler in two different ways, that is, for some where and . If this were the case, then we could rearrange the equation to get . If you interpret this equations, it says that we can knot together the different ropes of length and and get the same length as combining and (you can check that , which means they really are all distinct ropes being used). But then our ropes would not satisfy the bargeman’s overly-specific condition (well, it’s actually my or, more accurately, Sidon’s condition). This is a contradiction! So we must have made a Golomb ruler after all.

You can now try running the same argument in reverse to get the full proof. Frequently, in mathematics, when you have a two-way proof, the same argument in reverse doesn’t work, and another argument is needed.

The key, reversible step of the proof is also the very pedestrian secret of how the magic trick works.

The mathematics behind both the proof and trick are really simple when written out. But both lead to something, I at least, don’t find immediately obvious.