Combinatorics: Lock puzzle , minimum combinations 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?
 A: 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.
A: 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$.
