Let us call a nonnegative integer m a mark. A ruler R is a strict increasing finite sequence of marks. (By convention the first mark is set to 0.)
The number of marks of the ruler R will be denoted by MR and the distance (i.e. absolute difference) between the last and the first mark is the length of the ruler LR. A segment of a ruler is the space between two adjacent marks; a ruler with M marks has S = M - 1 segments.
By convention, we call the ruler with no segments the empty ruler and
a ruler, which length is equal to the number of its segments the trivial ruler.
The set of all distances a ruler can measure is
DR = { d | d = |m' - m''| with m' =/= m'' in R }
We call a ruler R complete iff DR = {1,2,3,...,n} for some integer n. In other words, given a distance d with 1 <= d <= LR we can find two marks m and m', such that m < m' and d = m' - m.
Complete rulers with extremal properties are of particular interest:
We call a ruler R marker-minimal iff R is complete and there is
no complete ruler with the same length which possesses less marks.
We call a ruler R length-maximal iff R is complete and there is no complete ruler with the same number of marks which has a greater length.
Examples
R = [0,1,2,8,14,30,41,47,63,74,79,84,89,94,97,98,99]
R is a ruler with 17 marks, which can measure all distances between 1 and 99. Hence it is a complete ruler. However R is not an length-maximal ruler, because
S = [0,1,2,8,14,25,36,47,58,69,80,85,90,95,98,99,100]
is also a complete ruler with 17 marks, but can measure all distances between
1 and 100. But even S is not a length-maximal ruler!
A length-maximal ruler is not necessarily unique. For example
R = [0,1,2,6,9] and S = [0,1,4,7,9]
are both length-maximal complete rulers with the same distance set
DR = {1,2,3,4,5,6,7,8,9} = DS.
Another example: There are 9 marker-minimal rulers with 3 segments.
{ [0,1,2,4], [0,2,3,4], [0,1,3,4], [0,1,3,5], [0,2,4,5],
[0,1,2,5], [0,3,4,5], [0,1,4,6], [0,2,5,6] }.
Even more examples can be found in this table with one example of a marker-minimal ruler for each length L with 1 <= L <= 101.
Let us denote the set of all complete rulers which are of length L and have S segments by R[L, S], where L >= 0 and S >= 0. Further we denote the number of complete rulers by C[L, S] := card(R[L, S]).
Note that we use the number of segments rather than the number of marks as the secondary id. This convention simplifies many formulas and gives for example C[L, L] = 1 (counting the trivial ruler of length L).
C[L, S] - The Number of Complete Rulers.
0|1
1|0,1
2|0,0,1
3|0,0,2,1
4|0,0,0,3, 1
5|0,0,0,4, 4, 1
6|0,0,0,2, 9, 5, 1
7|0,0,0,0,12,14, 6, 1
8|0,0,0,0, 8,27, 20, 7, 1
9|0,0,0,0, 4,40, 48, 27, 8, 1
10|0,0,0,0, 0,38, 90, 75, 35, 9, 1
11|0,0,0,0, 0,30,134,166, 110, 44, 10, 1
12|0,0,0,0, 0,14,166,311, 277, 154, 54, 11, 1
13|0,0,0,0, 0, 6,166,490, 590, 431, 208, 65, 12, 1
14|0,0,0,0, 0, 0,130,660,1096,1022, 639, 273, 77, 13, 1
15|0,0,0,0, 0, 0, 80,800,1816,2132,1662, 912, 350, 90, 14, 1
16|0,0,0,0, 0, 0, 32,790,2641,3980,3796,2574,1262, 440,104, 15, 1
17|0,0,0,0, 0, 0, 12,710,3476,6721,7796,6371,3836,1702,544,119,16, 1
LS|0|1|2|3| 4| 5| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14| 15|16|17|
This is sequence A103294 in the Online Encyclopedia of Integer Sequences. In the triangle the length of the rulers increase from top to bottom and the number of segments increase from left to right. Entries above the main diagonal are 0.
In the above triangle the marker-minimal rulers are counted by the first nonzero numbers in a row and the length-maximal rulers are counted by the last nonzero numbers in a column. These numbers are displayed in red color. A more convenient way to look at this sequence is provided by this list.
As a first important observation we note the following fact.
Theorem 1. A complete ruler, which is length-maximal, is also marker-minimal.
On this basis we understand the following more convenient parlance.
We call a ruler R perfect, iff R is marker-minimal.
We call a ruler R optimal, iff R is marker-minimal and length-maximal.
Note that we regard the empty ruler being length-maximal.
We haven't said yet anything about the existence of perfect and optimal rulers. The next observation is a way to affirm their existence.
Theorem 2. Each row and each column of the matrix C[L, S] has only finite many entries different from 0.
Moreover, if S <= L and C[L, S] = 0 then C[K, S] = 0 for all L <= K
and C[L, N] = 0 for all N <= S. This gives us a computational strategy
to show that a ruler R is perfect respectively optimal:
R is perfect iff R is in R[L, S] and C[L, S-1] = 0.
R is optimal iff R is in R[L, S] and C[L+1, S] = 0.
Simple questions, not easy to answer, are:
If L is the length of a ruler, for what integers L are marker-minimal rulers also length-maximal? In other words: For what integers L exist optimal rulers with length L?
1,1,3,6,9,13,17,23,29,36,43,50,58,68,79,90,101,112,123
[0 <= L <= 18]
This is sequence A004137 in the Online Encyclopedia of Integer Sequences.
Find an algorithm to generate all perfect rulers R with length L.
The sequence of the number of all optimal (length-maximal) rulers with S segments starts:
1, 1, 2, 2, 4, 6, 12, 4, 6, 2, 2, 4, 12, 4, 2, 2, 2, 2, 4
[0 <= S <= 18]
This is sequence A103299 in the Online Encyclopedia of Integer Sequences.
Next we give the number of all perfect (marker-minimal) rulers with S segments:
1, 1, 3, 9, 24, 88, 254, 1064, 1644, 3382, 4156,
8022, 26264, 52012, 25434, 8506, 5632, 6224, 12330
[0 <= S <= 18]
This is sequence A103301 in the Online Encyclopedia of Integer Sequences.
The number of perfect (marker-minimal) rulers with length L starts:
1, 1, 1, 2, 3, 4, 2, 12, 8, 4, 38, 30, 14, 6, 130,
80, 32, 12, 500, 326, 150, 66, 18, 4
[0 <= L <= 23]
This is sequence A103300 in the Online Encyclopedia of Integer Sequences.
A more complete table can be found here, which lists the number of perfect rulers with length 0 <= L <= 123. As far as I know this is the most complete list of values ever published on this topic.
Complete rulers with different length may have the same number of segments. So we may ask: How many different lengths are associated with the same number of segments? The answering sequence starts:
1, 1, 2, 3, 3, 4, 4, 6, 6, 7, 7, 7, 8, 10, 11, 11, 11, 11, 11
[0 <= n <= 18]
As innocent as this sequence appears, it is very hard to compute the next number in this sequence. So it is a good candidate for inclusion in the Online Encyclopedia of Integer Sequences. Look here A103297 to see if someone has found more entries. The next values conjectured by me are on this page: 15, 15, 15, ...
Closely related to the last sequence is the mapping length -> segment, associating the number of segments of a complete ruler with its length. This sequence starts
0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7
[0 <= n <= 18]
This is sequence A103298 in the Online Encyclopedia of Integer Sequences.
I would like to thank Klaus Nagel, Rainer Rosenthal, Alfred Heiligenbrunner and Hugo Pfoertner for checking the figures. 2003-01-03 (updated 2005-01-03)