The Broken Combination Lock problem

(well...*one* of the broken bicycle lock problems)
(AKA rooks on a 3-D chessboard problem)

You have a combination bike lock of the type which has 3 rings, each with numbers 1 through 8. Normally with this kind of lock you have to line up 3 numbers in the right order to open it. The number of possible combinations is 8x8x8.

But, this lock is broken in such a way that you only have to match any 2 of the 3 numbers in order to open it. Obviously you could do it in 64 tries (8x8) by just using any 2 of the rings, but surely you can do better than that.

1. What is the minimum number of combinations you have to try to ensure that you can open the lock?

2. What is the general solution for a 3-ring lock 'broken' as above, but with 'n' numbers on each ring
 a) if 'n' is even?
 b) if 'n' is odd?

(This is the same type of problem as the 'rooks on a 3-dimensional chessboard'. It is known that N rooks may be placed on a 2-dimensional NxN chessboard so that every square is controled by at least one rook. What's the minimal number of rooks on 3-D chessboard NxNxN to meet this condition?)

One thing I found interesting was how to visualize this problem. Basically, you start with an 8 x 8 x 8 cube. Each guess at a combination 'cuts out' a line of 1 x 1 x 1 cubes in each of the 'x', 'y' and 'z' directions from the specific (x, y, z) cube selected. That is, if you select a cube - say (1,1,1) - then you are selecting all cubes that have the same x,y but a different z (the vertical bar in the diagram below), all cubes that have the same x,z but different y (the bar going into the page) and all cubes that have the same y,z but different x (the bar going left to right). Together, these make a '3-dimensional L' shape.

Here's a diagram (it's 4 x 4 x 4, but you get the idea).

In this case, you can see that all guesses where (say) x, y, z <= 2 will carve out a larger '3-dimensional L' shape.

So you only need to make guesses in the x, y, z <= 2, plus (from symmetry) guesses in the x, y, z >= 3 quadrant to complete the solution.

To help visualize, think of a 2 x 2 x 2 cube first. If you pick (1,1,1) and then (2,2,2) you make two '3-dimensional L' shapes that cover the entire cube.

Now looking at the 4 x 4 x 4 cube...the number of guesses you need to cover the x, y, z <= 2 quadrant cannot be less than 4 (the area of any 2 x 2 'end' to the 3-dimensional L). It's easy to see there are many solutions of 4 (more on this later), so the full solution is (2x2)x2 = 8. And for an 8 x 8 x 8 cube the answer is (4x4)x2 = 32.

For an n x n x n cube where n is even, this gives (n/2)(n/2)x2 = (n**2)/2.

If n is odd, a similar approach gives the solution (noting that the two quadrants you are selecting in should be as near to the median as possible, so for a 9 x 9 x 9 cube you could select 16 guesses in the x, y, z <= 4 quadrant, and 25 guesses in the x, y, z >4 quadrant.

For an n x n x n cube where n is odd, this gives ((n-1)/2)**2+((n+1)/2)**2 = (n**2+1) / 2

And finally, the reason that the two quadrants should be the same size (if n is even) and as close as possible to the same size (if n is odd) is simply because the (sum of the) products of the sides of the quadrant (i.e. the sum of the area of one side of each quadrant) is a minimum in that case. 'An exercise left to the reader' - though I can send you the math if you want. See also my next post.

Next post will look at how to generate specific solutions, and more on why you need to select these 3-dimensional L's as close in size as possible to each other to minimize the number of guesses needed in the solution.

And it is nowhere near to clear (to me) for n x n x n x n. More on that even later.