Introduction.
Rulers, which we can buy at the stationery shop, are edged with a regular sequence of marks and look somewhat like this
'-'-'-'-'-'-'
Rather dull. Recently, however, the manufacturers of rulers found out that they can reduce production costs by deleting some of the
marks from the rulers without reducing their functionality. For example with the ruler
'-'---'--'
you can also measure all the distances you can measure with the standard ruler of equal length.
How many marks can be deleted, if we want to be able to measure all distances up to some length? In essence, it is this question
which we are going to study here and which turns a monotonous ruler in an interesting object of combinatorics.
First of all, we want to be sure that we can measure all length of equal or shorter size then the length of the ruler. Clearly this
is a sine qua non for a reasonable ruler. A ruler which has this feature will be called a complete ruler, because it has enough
marks to fulfill this basic task. Rulers which can not (incomplete rulers) will not be considered here.
Next we focus on those complete rulers which have as few marks as possible. They will be called perfect rulers. They are complete
rulers, but the deletion of a single mark would make them incomplete. There is a certain aesthetic impression associated with perfect
rulers: they accomplish a task with a minimum of complexity.
Interestingly, perfect rulers with the same number of marks still differ in their usefulness. Let us consider the following three
perfect rulers. All of them have 4 marks. (The numbers correspond to the positions of the marks on the ruler.)
[0, 1, 3, 4], [0, 1, 3, 5], [0, 1, 4, 6]
But with the third one you can measure 33% more lengths compared to the first one. So you would certainly choose the third one if
you would like to buy one of these rulers.
But the decisive thing about the third ruler is that there does not exist any other ruler with 4 marks, which is complete and can
measure more lengths. Thus the marks cover a maximal metering range. Rulers with this quality are called optimal rulers. Optimal rulers
thus combine the aesthetics of a minimum of complexity with a maximum of usefulness.
Rulers with this feature are quite rare creatures. For example there are 52012 perfect rulers with 14 marks, but only 4 out of them are
optimal rulers. The enumeration of complete, perfect and optimal rulers will be one of our major tasks.
Optimal rulers, which exist for every number of marks, have a very peculiar length. In fact their lengths are, in dependency on the
number of marks,
0, 1, 3, 6, 9, 13, 17, 23, ...
But these numbers also count the maximal number of edges in a graceful graph on n nodes, linking
the study of perfect rulers to graph theory, combinatorics and additive number theory.
Clearly we would like to know how to construct such optimal rulers. At first sight this does not seem to be an easy task, but there
is an exciting, still unproved conjecture, that there is a blueprint for optimal rulers, which would allow a very simple construction.
It says that a ruler with more then 14 marks is optimal only if it is a Wichmann-ruler, named after B. Wichmann, who introduced
them in 1962 in A note on restricted difference bases. |