# Rulers!

Rulers have been around a long time for measurement but are they efficient tools?   A typical ruler will have many pairs of marks between which a specific length can be measured and this could be viewed as inefficient if, for example, the cost of making marks was very costly.

The coverage of rulers given here is the result an interest inspired by the following old Sunday Times puzzle:

Sunday Times Brain Teaser 560

Published on 26 March 1972

The draper sells ribbon by the inch. His counter is exactly 100 inches
long, and he has marked it off into sixteen segments: six of 11 inches
together near the middle (he must think 11 inches make a foot!), two of
6 inches, three of 5 inches, one of 3 inches, and four of 1 inch. That
way he can measure any number of inches up to 100, by picking the right
pair of marks.

Of course one of the 1-inch lengths has to be at one end, or he wouldn’t
be able to measure 99 inches. In fact, two of them are at the same end,
which is how he measures 98 inches. Can you work out how the segments
are arranged?

Because we are told the positions of the one and six inch segments, it is not too hard to solve this puzzle in Python:

This gives two solutions for the positions of the segments, one being:

(1, 1, 3, 5, 5, 5, 11, 11, 11, 11, 11, 11, 6, 6, 1, 1)

and the second its reverse.  If we rewrite this in terms of the positions of the marks (including the two ends of the ruler) we obtain a ruler with seventeen marks:

[0, 1, 2, 5, 10, 15, 20, 31, 42, 53, 64, 75, 86, 92, 98, 99, 100]

But could we have solved this problem if we had not been given the positions of some of the segments?  Moreover, although we have a solution for measuring all integer values between 0 and 100 inclusive with a seventeen mark ruler, is it possible to do this with less than seventeen marks?

My first step in trying to answer these questions was with this Python program:

which considers rulers with increasing numbers of marks, to find their maximum lengths. It produces the following results:

$\begin{array}{|c|c|r|}\hline Number\;of\;Marks & Max\;Ruler\;Length &Time\;(ms) \\ \hline 3 & 3 & 0 \\ \hline 4 & 6 & 0 \\ \hline 5 & 9 & 1 \\ \hline 6 & 13 & 2 \\ \hline 7 & 17 & 7 \\ \hline 8 & 23 & 99 \\ \hline 9 & 29 & 1,727 \\ \hline 10 & 36 & 38,734 \\ \hline 11 & 43 & 701,800 \\ \hline \end{array}$