Puzzle of the Week for 11 January 1999: Solution

The best strategy for using two bits will require at most 11 tests, at a cost of $110. If additional bits can be made for $10 each, the best strategy will require at most one extra bit and 7 tests, at a cost of $80.

To discover these strategies, it's easiest to work backwards. Consider first how many tests are needed to distinguish between n possible values of maximum speed if we have only one bit:
Number of speeds testable
Number of tests One bit
1 1
2 2
3 3
... ...
n n

Using only one test, we can test only one speed, no matter how many bits we have:
Number of speeds testable
Number of tests One bit Two bits Three bits Four bits
1 1 1 1 1

Now, let's combine the tables above:
Number of speeds testable
Number of tests One bit Two bits Three bits Four bits
1 1 1 1 1
2 2 ? - -
3 3 - - -
... ... - - -
n n - - -

How can we fill in the cell marked with "?" above? This cell corresponds to the case in which we have a "budget" of two bits and two tests. The number we seek is the number of speeds we can distinguish without exceeding our budget. If we test the first bit at (say) 1000 rpm, there are two possible outcomes. If the bit fails, we have one remaining bit and one remaining test, and the red cell above and to the left of the "?" shows that we can test just one more speed in that case (for example, at 500 rpm). On the other hand, if the bit passes, we have two remaining bits and one remaining test, and the green cell directly above the "?" shows that we can test one more speed (say, 1400 rpm) in that case. The number we seek is therefore one plus the numbers in the red and green cells (in this case, 3). Note that the choice of speeds to test is more or less arbitrary so far, except that the second test should be at a lower speed if the first one fails, or at a higher speed otherwise, in order to avoid redundancy.

Let's try this again:
Number of speeds testable
Number of tests One bit Two bits Three bits Four bits
1 1 1 1 1
2 2 3 - -
3 3 ? - -
... ... - - -
n n - - -

This time, the cells above-and-left (in red) and above (in green) the "?" contain 2 and 3, so the "?" can be replaced by 2 + 3 + 1, or 6. Continuing in this way, we can complete the table:
Number of speeds testable
Number of tests One bit Two bits Three bits Four bits
1 1 1 1 1
2 2 3 3 3
3 3 6 7 7
4 4101415
5 5152530
6 6214156
7 7286398
8 83692162
9 945129255
101055175385
111166231561

Since the problem requires that we be able to identify the maximum speed from among 60 possible speeds, the cells that have been colored in above show the smallest numbers of tests needed to distinguish at least 60 speeds, given two, three, or four bits. Thus we find that strategies using two bits and at most 11 tests, or three bits and at most 7 tests, are possible.

How, then, can we determine what the strategy should be, knowing that it's possible to distinguish 66 speeds using two bits and 11 tests? Consider what happens if the first test fails: we have 1 bit and 10 tests left, so we can test at most 10 speeds. This implies that the first test should be at speed 11 (i.e., 1100 rpm), so that (in case of failure) we will be able to determine the speed in the range of speed 1 (100 rpm) to speed 10 (1000 rpm). If the first test succeeds, we can try another with bit 1; if that one fails, we have 1 bit and 9 tests left, so we can test at most 9 speeds. This implies that the second test with bit 1 can be 10 speeds above the first test, or speed 21 (2100 rpm). If the second test also succeeds, the third test is 8 speeds beyond the second; the fourth test is 7 speeds beyond the third, and so on.

The three-bit strategy can be worked out in much the same way, using the table above. If the first test fails, we have two bits and 6 tests left, which allow us to distinguish 21 speeds; therefore the first test should be at speed 22 (2200 rpm). If the first test succeeds, and the second test fails, we have two bits and 5 tests left, sufficient for testing 15 speeds; therefore the second test is at 16 speeds beyond the first in this case (speed 22 + 16, or speed 38, i.e., 3800 rpm).

Try to work out these strategies from the table before looking at the detailed solution. Can you prove that no larger number of bits will yield a less expensive test?

Links