Faulty Combination Lock

There is a 3 dial combination lock, where each dial features numbers 1 through 8 inclusive. However, it is poorly designed, and will open as long as at least two dials are correct. How many combinations does one need to try to guarantee opening the lock?

You can certainly succeed in $64$ tries, by guessing until you get the first two dials correct. Also, each guess only works on $22 (= 1 + 3*7)$ combintations: the exact match and ones where any of the 3 dials is any of the other 7 numbers. So it will take at least $8^3/22\ge 24$ guesses. So the optimal number is somewhere between $24$ and $64$, but where?

Source: Winkler, Mathematical Mind Benders.

• I assume each dial has "it's own" number, i.e., it's not just getting two out of three numbers without regard of which dials do you use? – dmg Apr 7 '15 at 7:04
• @dmg That is correct, order matters – Mike Earnest Apr 7 '15 at 7:14
• Did you mean 28 instead of 22? – Mohit Jain Apr 7 '15 at 7:22
• @MohitJain I think it's 22 - 1 (the exact match) + 3*7 (if we leave out the respective dial). – dmg Apr 7 '15 at 7:38
• @dmg My bad, I missed it is 1 to 8 and not 0 to 9. – Mohit Jain Apr 7 '15 at 7:45

Here's a way to get

32 triples

that match any combination. I think this number is optimal but don't have a proof.

For four numbers (say 1,2,3,4), we can choose 16 triples so that any two indices uniquely determine the third. For example, take the triples that add to 0 modulo 4.

(1, 1, 2)
(1, 2, 1)
(1, 3, 4)
(1, 4, 3)
(2, 1, 1)
(2, 2, 4)
(2, 3, 3)
(2, 4, 2)
(3, 1, 4)
(3, 2, 3)
(3, 3, 2)
(3, 4, 1)
(4, 1, 3)
(4, 2, 2)
(4, 3, 1)
(4, 4, 4)

Now, do the same with 5,6,7,8, and combine the two sets to get 32 triples. Given any triple, it matches one of the 32 triples because:
- At least two of the numbers are at most 4, which matches a triple in the first set with the remaining number wrong, or
- At least two of the numbers are at least 5, which matches a triple in the second set with the remaining number wrong

• I am somehow finding it hard to follow your argument. – Abhijit Apr 7 '15 at 7:57
• Basically, that set of triples covers all the possible doubles among them. – Joe Z. Apr 7 '15 at 8:00
• You got it right. – Mohit Jain Apr 7 '15 at 8:08
• This answer is clear and correct :) I'm going to hold off accepting to see if someone can get a proof of optimality, since I think that is half the fun. – Mike Earnest Apr 8 '15 at 0:09
• See this answer for proof of lower bound. – Mike Earnest Jul 15 '15 at 22:51

So, since this is a 3-number lock, I tried to think of it in 3D, where you're hunting for a point, and when you check a point, rays go out from it in the cardinal directions. (So, a weird 3D battleship).

I got

32 checks.

My reasoning is that you can think of the area space as 8 4x4 cubes. The cross-area of each cube is 16. It takes 16 guesses to fully check the 3 cross areas of the cube, but in doing so, you've checked the 3 adjacent 4x4 cubes.
Repeating on the opposite 4x4 cube, you've checked all the places, so 32 total guesses.

I tried to see if I could optimize it down, like use the same strategy for splitting each 4x4 into 2x2 cubes, but that left gaps that weren't checked.

I'll go ahead and try my hand at a proof of optimality.

The lock has three numbers; we will call the first the $x$-coordinate, the second the $y$-coordinate, and the third the $z$-coordinate. It helps to think like JonTheMon said, of a 3D version of battleship, but I won't refer specifically to this intuition.

Let's start with an easier example. Suppose the $y$ and $z$ coordinates must be from the numbers $\{1, 2, 3\}$ instead of $\{1, 2, .., 8\}$, but the $x$-coordinate could be any number from $\{1, 2, ..., 8\}$, which is 72 total possibilities. Can this be done with only 6 checks? Well, no. By the pigeon hole principle, there must be some $x$ coordinate, say $x = 1$, such that none of the checks start with $x = 1$. But the nine possibilities that start with one ($(1, 1, 1)$, $(1, 1, 2)$, $(1, 1, 3)$, $(1, 2, 1)$, etc.), must be covered by six checks, and each check can only cover one possibility. Hence it is impossible to do this easier problem with six checks.

Now to the full problem. Suppose only 31 checks are needed to open the lock. By the pigeon hole principle, there must be some number $x$ between $1$ and $8$ such that only three of the checks start with the number $x$. Without loss of generality, assume $x = 1$. Let's say these three checks are $(1, y_1, z_1)$, $(1, y_2, z_2)$, and $(1, y_3, z_3)$. Since there are five numbers not in the set $Y = \{y_1, y_2, y_3\}$ and five numbers not in the set $Z = \{z_1, z_2, z_3\}$, that makes $25$ combinations that start with $1$ not covered by these three checks. Each of these $25$ possibilities require distinct checks, and furthermore these $25$ distinct checks must have neither their $y$ nor $z$ coordinate in $Y$ or $Z$ respectively.

This means the 72 combinations$^*$ of the form $(x, y, z)$ for $x \in \{1, 2, .., 8\}$, $y \in Y$, and $z \in Z$ are covered by just six checks (since the other 25 can only have the $x$-coordinate correct for these 72 combinations). But this is impossible, as we've already demonstrated. QED.

$*$: Note that the above assumes $y_1 \neq y_2$, $y_1 \neq y_3$, $z_1 \neq z_2$, etc. But if any of these $y$ or $z$ values were the same, then there would be at least $30$ possibilities not covered instead of $25$, which is clearly impossible.

• Well done, you've finally put this old problem to rest! I wish I could accept your and xnor's answers, since they are each half the battle. – Mike Earnest Jun 22 '15 at 16:13

32

Because and this for me was the most simple reason:

If you had only 2 dials, you would need to try all combinations 1 with 1-8, then 2 with 1-8, etc.

But because you have 3 dials, which would look like this:

1 2 3

You could set dials 1 and 3 to 4 different sets of numbers (e.g. 1 and 8, 2 an 7, 3 and 6, 4 and 5) and then just spin the middle dial one through eight.

so 4 * 8 = 32