A Weird Kind Of Ruler


I ran across something neat. It’s something I’ve seen before, but the new element is that I have a name for it. This is the Golomb Ruler. It’s a ruler made with as few marks as possible. The marks are supposed to be arranged so that the greatest possible number of different distances can be made, by measuring between selected pairs of points.

So, like, in a regularly spaced ruler, you have a lot of ways to measure a distance of 1 unit of length. Only one fewer way to measure a distance of 2 units. One fewer still ways to measure a distance of 3 units and so on. Convenient but wasteful of marks. A Golomb ruler might, say, put marks only where the regularly spaced ruler has the units 1, 2, and 4. Then by choosing the correct pairs you can measure a distance of 1, 2, 3, or 4 units.

There’s applications of the Golomb ruler, stuff in information theory and sensor design and stuff. Also logistics. Never mind those. They present a neat little puzzle: can you find, for a given number of marks, the best possible arrangement of them into a ruler? That would be the arrangement that allows the greatest number of different lengths. Or perhaps the one that allows the longest string of whole-number differences. Your definition of best-possible determines what the answer is.

As a number theory problem it won’t surprise you to know there’s not a general answer. If I’m reading accurately most of the known best arrangements — the ones that allow the greatest number of differences — were proven by testing out cases. The 24-mark arrangement needed a test of 555,529,785,505,835,800 different rulers. MathWorld’s page on this tells me that optimal mark placement isn’t known for 25 or more marks. It also says that the 25-mark ruler’s optimal arrangement was published in 2008. So it isn’t just Wikipedia where someone will write an article, and then someone else will throw a new heap of words onto it, and nobody will read to see if the whole thing still makes sense. Wikipedia meanwhile lists optimal configurations for up to 27 points, demonstrated by 2014.

And as this suggests, you aren’t going to discover an optimal arrangement for some number of marks yourself. Unless you should be the first person to figure out an algorithm to do it. It’s not even known how complex an algorithm has to be. It’s suspected that it has to be NP-hard, though. But, while you won’t discover anything new to mathematics in pondering this, you can still have the fun of working out arrangements yourself, at least for a handful of points. There are numbers of points with more than one optimal arrangement.

(Golomb here is Solomon W Golomb, a mathematician and electrical engineer with a long history in information theory and also recreational mathematics problems. There are several parties who independently invented the problem. But Golomb actually did work with rulers, so at least they aren’t incorrectly named.)

Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there. He/him.

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.