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!
This is a real problem that was sent around my former maths department. The inquirer had a boat, and he wanted ropes of various lengths to knot together to moor his canal barge (I think each rope may have somehow used an eye splice for knotting). This is more or less the e-mail as I received it:
“I have 5 pieces of rope of length:
- 1 x 10 metres
- 2 x 12 metres
- 2 x 40 metres
I want to be able to cut the ropes into pieces of different lengths and to be able to tie combinations of these together to make longer lengths.
Is there a formula to obtain the optimum number and lengths of pieces ropes (i.e. the minimum number of pieces of ropes to give the most possible combinations of lengths of rope!). The minimum length of rope I need is 6m.”
Being more or less a combinatorial problem, I doubted whether any nice formula existed (or that it would be any more useful than a specific solution!). So, wanting to help, I cheated slightly, and chatted to the guy to get a bit more info. After our discussion, he decided that he wanted ropes with at most two knots (ie. three pieces), and to be able to make lengths at intervals of one or two metres. He also was quite keen on having a 20m rope.
I’ve given some additional assumptions and my solution below. But please have a go first: you may come up with a better way of doing it!