- #1
onomatomanic
- 103
- 1
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! :)
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! :)