Minimal Rulers — alaricstephen.com

Aug 16

Aug 16 Minimal Rulers

A normal ruler with lots of markings on it is actually overkill, you can make do with a smaller number of markings and still be able to measure any distance smaller than the length if the ruler itself. For example if you had a ruler like the one below:

Then you could use it to measure any distance from 1 to 6. For instance, to measure a distance of 3 you can use the distance between the marks at 1 and 4. We call these optimal rulers because they measure every distance smaller or equal to themselves.

  
    Marks
    Max Length
    Sample Solution
  

    2
    1
    [0,1]
  

    3
    3
    [0,1,3]
  

    4
    6
    [0,1,4,6]
  

    5
    9
    [0,1,2,6,9]
  

    6
    13
    [0,1,2,6,10,13]
  

    7
    17
    [0,1,2,3,8,13,17]
  

    8
    23
    [0,1,2,11,15,18,21,23]
  

    9
    29
    [0,1,2,14,18,21,24,27,29]
  

    10
    36
    [0,1,3,6,13,20,27,31,35,36]
  

Marks	Max Length	Sample Solution
2	1	[0,1]
3	3	[0,1,3]
4	6	[0,1,4,6]
5	9	[0,1,2,6,9]
6	13	[0,1,2,6,10,13]
7	17	[0,1,2,3,8,13,17]
8	23	[0,1,2,11,15,18,21,23]
9	29	[0,1,2,14,18,21,24,27,29]
10	36	[0,1,3,6,13,20,27,31,35,36]

There are some patterns that we can notice here. We you first start constructing them for the smaller numbers of marks they are trivial, with the first one just being two marks one unit apart. Each time you add another mark it can potentially add one more distinct distance with each previous mark, so adding in the third mark managed to make two new distances. Adding in one more mark (the fourth one) and it can interact with the other three making a total of six distances. What we have here are the triangle numbers, where the general term for n marks is n(n-1)/2. This serves as an upper bound for the maximum total length of a ruler with n marks.

But it is only the upper bound because it is sometimes not possible to lay the marks out without repeating one of the distances. I spent about quarter of an hour trying to lay out 5 marks to make a total length of 10 this morning, trying to carry on the triangle number pattern. Eventually I'd brute forced through the potential match ups without success, but I had found a solution for the 9 case. After this I turned to the internet.

It turns out that the higher you go, the further the optimal solution gets from our upper bound and it does so in a chaotic manner. No general formula has yet been derived for the maximum length with n marks. These solutions are generally not unique (ignoring that each of them can be mirrored to generate twice as many solutions), for instance the 5 mark case has another solution with [0,1,4,7,9]. These sort of numeration problems tend to grow in complication quickly and the large values are all worked out by computers rather than any grand theory.