Faulty Combination Lock

Question

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?

Please hide your answer, or at least the number in question.

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

The answer is

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