PERFECT AND OPTIMAL RULERS
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.

Rulers in a Nutshell

A ruler is a strict increasing finite sequence of marks, which are understood as nonnegative numbers. By convention the first mark is set to 0.

Rulers are counted with regard to their length L and the number of segments S (a segment is the space between two adjacent marks). A ruler with M marks has S = M - 1 segments.

A ruler is:

  • COMPLETE, if all distances d with 1 <= d <= L can be measured with the ruler.
     
  • PERFECT, if there is no complete ruler with the same length which possesses fewer marks.
     
  • OPTIMAL, if there is no perfect ruler with the same number of marks which has a greater length.
home Back to the Homepage of
Combinatorial Rulers