|PERFECT AND OPTIMAL RULERS|
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.
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.
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:
|Back to the Homepage of