Post Go back to editing

# KCC's Quizzes about Golomb rulers

A Golomb ruler is a ruler with a set of marks at integer positions such that no two pairs of marks are at the same distance apart. It has been studied by Salomon W. Golomb, Sidon and Babcock. The theory behind the Golomb set of values are used in radio frequency selection, in radio antenna placement and in current transformers

Each ruler can be characterized by:

1. The first mark is always 0
2. Its order : number of marks
3. Its length : distance between the 2 marks at the extreme sides
4. The ruler is said perfect when all the distances (integer) can be measured from 0 up to its end
5. The ruler is said Optimal if no shorter Golomb ruler of the same order exists

The above right picture shows a Golomb ruler of order 4, length 6 and is perfect and optimal. For example, it can measure all the distances from 0 to 6. 1 between marks 0 and 1, 2 between marks 4 and 6, 3 between marks 1 and 4, 4 between marks 0 and 4, etc… up to 6 between marks 0 and 6

Questions:

1. What are the order and the length following Golomb ruler? Is it perfect and optimal?

2. Find at least one Golomb ruler of order 5 and of length below or equal to 13 and that is optimal.

P.S. If you think there are still colleagues or friends (internal or external) you think who can be interested in those quizzes, please let let them know....

Kuo-Chang

Parents
• 1.

Order 4, length 7, not perfect (cannot measure 5) and so, not optimal either. (I assume that to be optimal it must be perfect in the first place.)

2.

I got 6 of them of order 6, length 13:  (1, 2, 6, 10), (1, 4, 5, 11), (1, 6, 9, 11), (2, 4, 7, 12), (2, 8, 9, 12)  and (3, 7, 11, 12). 0 and 13 are not mentioned but they are implicit. Sure, if (a, b, c, d) works, then (13-a, 13-b, 13-c, 13-d) works too.

We canot have an optimal ruler of order 5, length >10 since with the markers:  0, u, v, w, L, we can measure, in addition to the obvious u, v, w, and L :  L-u, L-v, L-w, v-u, w-u and w-v, so, a maximum of 10 possible values, so 10 maximum possible different values.

There is no solution for L=10, order 5, confirmed by a query in Access. (Take all possible combinations of 3 different numbers from 1 to 9 inclusive, compute the 10 possible expressions given here up, COUNT the DISTINCT results, 9 is the maximum "reacheable" distinct values),

For L = 9, there are: (1, 2, 6), (1, 4, 7), (2, 5, 8) and (3, 7, 8)

For L = 8, we have (1, 3, 7), (2, 4, 7), (1, 5, 7), (1, 5, 6), (1, 4, 6), (2, 3, 7), (3, 6, 7) and (1, 2, 5)

For L = 7, (1, 4, 6), (3, 5, 6), (1, 2,4), .... [ 12 in all  ]

I may have made an error in my Access queries though, have barely double-check.

• Thank you Michel for your detailed development! Concerning your remark about a ruler to be perfect and optimal, I think their definitions don't forbid a ruler to be optimal without being perfect. On question 2, you might have missed the ruler (1,4, 9,11)....