Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I think you can't beat it, but I haven't fleshed out a format proof yet. Will post it as an answer if I get to it before someone else does. –  Dennis Meng Nov 27 '13 at 22:43
    
With three locks that each have two options, it's easy to directly show you cannot do better than that strategy just by directly counting every track. –  alex.jordan Nov 27 '13 at 22:52
    
Also, *formal, not format, haha –  Dennis Meng Nov 27 '13 at 22:56

3 Answers 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.

share|improve this answer

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.

share|improve this answer
    
Still nice to be corrected though. +1 –  Dennis Meng Nov 27 '13 at 23:24

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$.

share|improve this answer
1  
i think its wrong, we are talking about a deterministic solution here. sorry –  user106448 Nov 27 '13 at 21:55
    
I understand. This is "at least in terms of expected value". I think it's interesting but too much for a comment –  alex.jordan Nov 27 '13 at 21:57
    
I did the calculation for randomly choosing a combination to test excluding combinations you have already tried, and the expected value goes down to $22.3$. And after $64$ tries, there would be over a 95% chance that you would have cracked it. I know it's not what you are looking for, but I still think it's neat. –  alex.jordan Nov 28 '13 at 16:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.