Combinatorics: Lock puzzle , minimum combinations

Question

A safe has three locks of which every lock has 8 possibilities 1, 2 ...8. Safe gets opened if any 2 of 3 locks gets opened. So, a possible way to open safe is try 2 locks, for each possible pair of combinations giving us 64 combinations. Can it be done in lesser number of combinations? If so, what is the minimum number of combinations required?

Answer 1

There are $1+7+7+7=22$ configurations that open the safe. There are $8^3=512$ configurations total. If you just randomly try a configuration, it has $\frac{22}{512}$ chance of working. If you repeat, choosing random independent configurations over and over, you have an example of the geometric distribution, and the mean is $\frac{512}{22}\approx23.3$. So at least in terms of expected value, this is better than exhaustively searching through the first two lock combinations, where the expected value for the number of trials needed is $\frac{7}{8}32.5+\frac{1}{8}\frac{7}{8}4.5+\frac{1}{8}\frac{1}{8}1\approx28.9$.

Answer 2

The first combination you try rules out $22$ possibilities from the total of $512$. Ideally, each combination you try will rule out another $22$, for a total of $$\left\lceil \frac{512}{22} \right\rceil = 24$$ combinations.

However, we can't actually find a set of $24$ special combinations so that the possibilities they rule out are distinct. Below is a rather messy attempt.

---

Without loss of generality, we can assume that the first combination we try is $111$. This rules out $111$, $\text{A}11$, $1\text{B}1$, and $11\text{C}$, for digits $\text{A} \neq 1$, $\text{B} \neq 1$, and $\text{C} \neq 1$.

If we try $222$, $333$, and so on up to $888$, each of those attempts rule out $22$ possibilities as well. After these, we've ruled out $22 \cdot 8 = 176$ possibilities. Which possibilities are left? Exactly those with no repeated digits.

If we try $123$, we have an overlap with $121$, $122$, $113$, $133$, $223$, and $323$ being doubly ruled out, but we still rule out $22-6=16$ additional possibilities. We can get another $16$ ruled out by each of $456$, $781$, $234$, $567$, $812$, $345$, and $678$.

Now we have a total of $512 - 22 \cdot 8 - 16 \cdot 8 = 208$ possibilities left to rule out. These are exactly the combinations $\text{A}\text{B}\text{C}$ in which $\text{B} - \text{A} \not\equiv 0, 1 \pmod{8}$ and $\text{C} - \text{B} \not\equiv 0, 1 \pmod{8}$.

If we try $135$, we have an overlap with $133$, $155$, $535$, $335$, $115$, $131$, $145$, $235$, and $125$ but we still rule out $22-9=13$ additional possibilities. Similarly, we try $246$, $357$, $468$, $571$, $682$, $713$, and $824$, each ruling out $13$.

Now we have $512 - 22 \cdot 8 - 16 \cdot 8 - 13 \cdot 8 = 104$ possibilities left, with $24$ attempted codes.

If we try $147$, we have an overlap with $144$, $177$, $117$, $447$, $141$, $747$, $145$, $167$, $127$, $137$, $247$, and $257$, but we still rule out $22-12=10$ additional possibilities. Similarly, we try $258$, $361$, $472$, $583$, $614$, $725$, and $836$, each ruling out $10$.

Now we have $512 - 22 \cdot 8 - 16 \cdot 8 - 13 \cdot 8 - 10 \cdot 8 = 24$ possibilities left, with $32$ attempted codes.

If we simply try each of the remaining $24$ codes, we have exhausted all possibilities (and so are guaranteed to open the lock) with $24 + 32 = 56$ tests, which is less than the proposed $64$.

$56$ is probably not the minimum number of tests necessary, but this shows that it can be done in less than $64$.

---

I apologize for the inelegance of this construction.

Answer 3

We can do it in $32$ tries as follows:

\begin{align} \begin{matrix} 111 & 222 & 333 & 444 \\ 123 & 142 & 134 & 243 \\ 231 & 214 & 341 & 432 \\ 312 & 421 & 413 & 324 \end{matrix} && \begin{matrix} 555 & 666 & 777 & 888 \\ 567 & 586 & 578 & 687 \\ 675 & 658 & 785 & 876 \\ 756 & 865 & 857 & 768 \end{matrix} \end{align}

The idea is that the first block of $16$ rules out all combinations with at least two numbers from $\{1, 2, 3, 4\}$ and the second block of $16$ rules out all combinations with at least two numbers from $\{5, 6, 7, 8\}$. By Pigeonhole Principle, any combination must have two numbers in one of these two sets, so we have covered all possible combinations.

---

Proof of Optimality

Assume on the contrary that $31$ tries are sufficient.

Lemma: For any position and any number $n \in \{1, 2, \ldots , 8\}$, we must have tried $\geq 3$ combinations with $n$ in that position.

Proof: By symmetry, it suffices to show that we must have tried $\geq 3$ combinations starting with $1$.

Assume on the contrary that at most two of the combinations tried start with $1$, then each rules out $15$ combinations starting with $1$, so we still have $64-2(15)=34$ possible combinations starting with $1$. All other combinations tried do not start with $1$, hence only rule out one combination starting with $1$, so we need to try at least $34$ more combinations, a contradiction.

Therefore we must have tried $ \geq3$ combinations starting with $1$.

---

If for each $n=\{1, 2, \ldots , 8\}$, we have tried $\geq 4$ combinations starting with $n$, then we require at least $32$ tries, a contradiction. Therefore for some $n$, we have tried at most $3$ combinations starting with $n$, hence by the lemma we have tried exactly $3$ combinations starting with $n$.

Now WLOG assume that $n=1$, by symmetry. So we have something like

$$\begin{matrix} 1ab \\ 1cd \\ 1ef \end{matrix}$$

where $a, b, c, d, e, f$ need not be distinct.

Note that all combinations of the form $1xy$ where $x \not =a, c, e$ and $y \not =b, d, f$ have not been ruled out.

If $a, c, e$ are not pairwise distinct, then there are at least $6$ choices for $x$, and there are at least $5$ choices for $y$, so we have $30$ combinations starting with $1$ which have not been ruled out. All other combinations we try do not start with $1$, hence rule out at most one of these $30$ combinations. Thus we need $\geq 30$ more combinations, making a total of $33$, a contradiction.

Therefore $a, c, e$ are pairwise distinct. Then there are $5$ choices for $x$ and at least $5$ choices for $y$, so there are $25$ combinations of the form $1xy$ which have not been ruled out, so we require $\geq$ $25$ combinations of the form $nxy$ (where $n \not =1$) to rule these out. That gives $28$ combinations tried so far.

Now note that by the lemma, we need to try at least $3$ combinations with $a$ in the middle, and we currently only have one such combination $1ab$ (all the $nxy$ combinations have $x \not =a$). Thus we need to try two more combinations with $a$ in the middle. Similarly, we need to try two more combinations with $c$ in the middle, and two more with $e$ in the middle, giving a total of $34$ combinations tried, a contradiction.

We conclude that we require at least $32$ tries, and this is indeed minimal by our construction at the start of the post.