Last week, Simon Gregg tweeted a couple of images of Golomb rulers. A Golomb ruler is a ruler with marks at integer positions such that distances are measured uniquely. In other words, no two pairs of marks are the same distance apart.
Today, Christopher Danielson tweeted about a different kind of minimally marked ruler. He wanted to use the minimum number of marks possible to measure all the distances from 1 to n on an n-unit ruler. So here, duplication of distances is fine, but all possible distances must be measurable.
For most n, it’s not possible to make a Golomb ruler that also measures all possible integer distances. For example, Danielson was looking at 12-unit rulers. We were able to show that five marks wasn’t enough to measure all distances 1 to 12 because five marks only result in ten pairs of marks, so one could only measure ten distances. That meant he had to use six marks, but six marks create fifteen pairs of marks and thus fifteen distances. A 12-unit ruler with six marks will then necessarily duplicate some distances.
There are some n where a Golomb ruler that measures all the distances could be possible, though. In particular, if n is a triangular number, then the number of pairs of marks would be exactly equal to the number of desired distances. But that doesn’t mean that it’s actually possible choose marks to make such a perfect Golomb ruler, though. I decided to investigate. Continue reading