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?
[Math] Combinatorics: Lock puzzle , minimum combinations
combinatoricspuzzle
Best Answer
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.