KCC's Quizzes about Golomb rulers

1. Order=4, Length=7. This ruler is not perfect (distance=5 is missing) and it is not optimal (e.g. the example ruler has same order but shorter length)

2. The ruler [0, 1, 4, 9, 11] is of order=5 and length=11 and is optimal. 

Hi Kuo-Chang,

Q1. It is order 4 as it has 4 division markings.  It can measure 1, 2 (3-1), 3, 4 (7-3), 6 (7-1) and 7 but not 5.  So, it is not optimal, because there is a shorter ruler of the same order, the one in the question, and not perfect as it cannot measure 5.

Q2. I found an optimal ruler with markings at 1, 4, 9 and 11 but it is not perfect as it cannot measure 6:

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.

I fail to see how we get 6.  It is not a marker, 1+6 is not a marker, 4+6 isn't, 9-6 neither 11-6.

And ChatGP confirms that there is no perfect Golomb Ruler of length 10, order 5.
So my Access query was probably right.  :-)

Thanks Gaetano for your prompt reply! And I can alreday tell you: bingo! You get it, congratulations!

For question 2: do you think the ruler is perfect?

Hello Michel, I suppose your remark to Gaetano is because 6 is not covered? And that's why that ruler is said optimal but NOT perfect...

Congratulation Martin! You get it and are (one more) among the very first ones!

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)....

Hi Kuo-Chang, the ruler of question 2 is NOT perfect (distance =6 is missing).