August 2009
—————————
In my August diary I posed the following brain-teaser:
You have a suitcase with a 3-digit combination lock on it. The digits range from 1 to 8 You can't remember the combination, but you do remember that the lock has always been defective in that as long as you have 2 out of 3 numbers in the right place, the suitcase will open. So if the correct combination is [2, 6, 3] then [?, 6, 3], [2, ?, 3] or [2, 6, ?] will open the suitcase.
What is the minimum number of combinations you must try to guarantee that you will open the suitcase?
—————————
Solution (from Michael Tarski, to whom many thanks)
First, let's set a lower bound on how many combinations need to be tested.
To do this, visualize all 512 combinations as gridpoints in an 8x8x8 cube (the first
digit becomes the Z coordinate, second digit Y coordinate, third digit X coordinate).
The bottom-most plane in this grid cube represents an 8x8 grid of the combinations
in the 100's: 111, 112, 113, … 187, 188.
Note all 64 points in this plane have the same Z coordinate (first digit). Any
gridpoint in this plane (representing a combination) that is tested, will also
test all other points in the same row or column of the plane, since points in
the same row share the same Y coordinate, and points in the same column share
the same X coordinate.
For the rest of this discussion, refer to the following grid with points labeled A, B, C, D:
C C C D D D D D
C C C D D D D D
C C C D D D D D
C C C D D D D D
C C C D D D D D
B B A C C C C C
B A B C C C C C
A B B C C C C C
Let's assume there are three combinations (gridpoints) tested that are in this plane.
These are labeled A. Testing A will also test all the points in the same rows and
columns as the A's, and these are marked with B's and C's. So far, we've identified
three testpoints in our solution.
None of the points marked D are tested by the three testpoints in this plane. They
need to be tested by points in the other planes (the gridpoints directly above them).
Thus, another 25 testpoints are needed (at a minimum) to test the D combinations,
bringing our total to 28.
In addition, in the planes above this plane, the points corresponding to the A's will
be tested (by the three testpoints in this plane), but none of the points labeled B
will be tested by any of the A's in this plane, nor by any of the D's in the other planes
(since no B is in the same row/column as any D). This requires another 6 testpoints to
cover the B's in the other planes, bringing our total to 34.
Summary, so far: if any plane contains only three testpoints, the entire solution must
require at least 34 testpoints.
If you do the same analysis for 2, 4, and 5 testpoints in any given plane, you'll see
that a minimum of 40, 32, and 34 total testpoints are needed, respectively. (The actual
formula for minimum testpoints needed, given A testpoints in a plane, is
(A2 + (8-A)2).
So, it appears that the lower bound is 32 testpoints, achieved with exactly four testpoints
in each plane. (Due to symmetry of the axes, this analysis applies whether we are talking
about the XY planes, YZ planes, or XZ planes).
With a little thought, I worked out the following solution of 32 test combinations, which
is optimal. Each of the 512 combinations differs by at most one digit from at least one
of the following set:
111 122 133 144
212 223 234 241
313 324 331 342
414 421 432 443
555 566 577 588
656 667 678 685
757 768 775 786
858 865 876 887