:: 01-Nov-2004 23:48 GMT (Monday) ::
With the completion of OGR-24, I thought I would draw a diagram of the
best ruler and talk a little bit about what it means.
The diagram can be found here: http://hewgill.com/ogr/ogr24.png
The top portion shows the ruler laid out to scale. The numbers (9, 24,
4, etc) are the distances between each mark. For various lengths
between 1 and 425 units, there is a unique way to measure that distance
using the ruler. The bottom section of the diagram shows how to use the
ruler to measure each possible distance.
For example, the distances 1, 2, 3, and 4 are trivially measured by
lining up with the corresponding distances in the ruler. 5 must be
measured by combining the 4 and the 1 (which are right next to one
another). 6 through 11 are easy because those distances are already
marked on the ruler, 12 must be measured by combining 10 and 2 (the
numbers are a little hard to read around that area, but you can compare
with the final published ruler).
The part that makes this a Golomb ruler is that there is exactly ONE
way to measure each distance. You can’t find any other combination of
distances in the given ruler that add up to say, a distance of 100,
except for 39+14+3+44. And the optimal part is that this is the
SHORTEST ruler (with respect to the overall length of 425) that offers
only one way to measure each distance. There exist longer rulers that
also have a unique way to measure each distance, and there are also
shorter rulers that end up having more than one way to measure some
distances. This ruler satisfies both properties.
Note that not every distance between 1 and 425 can be measured with
this ruler. It happens that 128 is the first distance that can’t be
measured with the given ruler. In all, only 276 of the distances
between 1 and 425 can be measured. The gaps in the lower portion of the
diagram indicate distances that can’t be measured.
Congratulations to all the participants who donated CPU time to prove
this result!