# Optimizing a Binary Ruler

1. Jun 27, 2015

### onomatomanic

Hello board,

in the course of a data processing project I'm working on, this challenge presented itself, and it's a bit beyond my firm grasp. Stripping away the non-essentials, what we have is this: Construct a binary ruler of length L=(2^n)-1 units, subdivided into the least number N of sections of lengths (2^m_i). A "ruler", for these purposes, being a linear object capable of measuring any integral distance D between two points, in the range from zero to L. And "measuring" meaning placing the ruler in line with the two points, such that both of them coincide with one of its subdivisional markings.

With regular real-world rulers, we use m_i=0 for all i and N=L, which is to say that there are markings for every unit, allowing us to measure any distance from either end. Here, this is not required, hence we can reduce N to well below L, by making some sections larger than others, just as long as we can find a pair of markings somewhere along its length which are D units apart.

To illustrate, my immediate thought for an optimized solution for L=2^3-1=7 was to subdivide the ruler into only three sections of lengths 2^0, 2^1, 2^2, which I shall write as [1|2|4]. I'm guessing this was an intuitive application of the solution to the similar problem in which you have three loose objects with those lengths, and place them end-to-end to measure distances between points, which I'd come across previously in some form or other (finding the smallest number of coins to be able to always make change, for a given set of denominations, IIRC). However, that intuitive solution doesn't quite work - the proposed ruler can measure any length in its range, except 5. The difference, quite simply, is that here, the sections occur in a fixed order. 5 would have to be measured as 1+4, but the ruler doesn't allow us to do that, because while both of those sections exist, they'd have to be neighbours as well to be usable, and unlike 1+2 and 2+4, they're not. Increasing N from 3 to 4 offers two working solutions, though, [1|2|2|2] and [1|1|1|4], or [ 1x1 | 3x2 ] and [ 3x1 | 1x4 ], to make the notation more convenient for future use.

Now, for even values of n, there appears to be a trivial-ish solution which may well also be the/an optimal one, but I'm having trouble proving that to myself. That solution takes the general shape [ ((2^(n/2))-1) x 1 | ((2^(n/2))-1) x (2^(n/2)) ], with N = 2*((2^(n/2))-1). For the first few values, that works out as

n=2 -> L=3 -> [1|2] @ N=2, naturally
n=4 -> L=15 -> [ 3x1 | 3x4 ] @ N=6, by trial-and-error, and computationally confirmed to be the (only) optimal solution in this case
n=6 -> L=63 -> [ 7x1 | 7x8 ] @ N=14, by extrapolation from the above, and computationally confirmed to be an optimal solution

For what it's worth, this "feels right" in as far as limiting the section lengths to two values avoids the problem of the sections needed for a given D being available per se, but not being next to each other, as with 5 in the [1|2|4] attempt. And once one accepts that limitation, it also "feels right" to pick 1 and the geometric mean of 1 and (L+1) as those two lengths, as well as to pick equal numbers of each.

However, that feeling isn't entirely to be trusted, because while there are apparently no solutions for n=6 and N<14, there are more than a dozen distinct ones at N=14, and none of the others are trivial in the least. This is the second-simplest I've found (haven't fully exhausted the billions of possibilities yet), in terms of simplicity and symmetry:

[1|2|1|2| 6x8 |4|2|1|2]

Similarly, for odd n, we have n=3 -> N=4 as per the earlier illustration, and n=5 -> N=10 computationally, both of which fall neatly between the previous results. In each case, two of those can again be called trivial in that they are merely prolonged or truncated variants of the adjacent even ones, thusly:

[1|2] => [1|2|2|2], [1|1|1|4] <= [1|1|1|4|4|4]
[ 3x1 | 3x4 ] => [ 3x1 | 7x4 ], [ 7x1 | 3x8 ] <= [ 7x1 | 7x8 ]

But again, starting with n=5, there are plenty of equally-valid alternatives with the same N, such as this one:

[1|4|2|8|2|8|1|2|1|2]

To me, this suggests that assuming that the trivial solutions will remain optimal in general is questionable at best, and I'd appreciate any more methodical insights. TIA! :)

2. Jun 27, 2015

### Staff: Mentor

What prevents you from measuring 1 unit and marking the endpoint and sliding the ruler 1 unit to the left, and then using the 4-unit interval to measure the rest?

3. Jun 27, 2015

### onomatomanic

Heh.

The actual reason has to do with those non-essentials I omitted because they have no bearing upon the problem in its abstract form. What it boils down to is that the point of this optimization is to improve efficiency (a ruler with fewer sections is computationally "cheaper" than one with more), and that by resorting to a multi-step procedure such as you describe, I'd more than likely throw that away, and then some.

I'm sure I can come up with something more interesting in the language of the ruler analogy. Like, the two points in question could be objects floating on the surface of a body of water, and making direct contact with that surface in any way would set them in motion? :P