»  Solutions to puzzles in my National Review Online Diary

  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