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.

There is a safe with three locks, like the ones in the hotel rooms that are opened with a "key" which is similar to a credit card. There are three keys, a correct one for one for each of the locks, but the correspondence is unknown. If only one or two keys are inserted into a lock, nothing happens; if all three keys are inserted,

(a) a wrong key closes the lock;

(b) the right key changes the status of the lock: if it was closed it becomes open, if it was open it becomes closed.

It is impossible to see if a single lock is open or closed, and of course the safe will be opened only if all locks are open. Is it possible to open the safe? If so, which is the minimum number of trials which is necessary to be sure to open eventually it? Assume that at the beginning the safe is not open, but you do not know which locks are closed, only that at least one of them is closed.

share|improve this question
1  
I have a solution that requires a maximum of 8 trials. Can anyone do better? –  ferson2020 Mar 27 '13 at 14:34
1  
Am I missing something? The question does not seem to say anything about how many keys you have available to try? I assume every key will physically fit in any lock? Or do you know which key matches which lock? –  Henning Makholm Mar 27 '13 at 14:43
1  
The minimum number of maximum trials is at least 7, since a unlocking the safe requires all 3 keys be in the right spot and that all 3 locks be closed before the correct sequence of keys is used. I suspect it can't be done in 7 though. –  ferson2020 Mar 27 '13 at 14:43
1  
@ferson2020: Yes, 7 is impossible, because every time you move from an even permutation of the keys to an odd one, one key will be left in its position, so the first try you make with a new parity will never succeed. Therefore you need to waste one attempt at the beginning, and later another one to switch parity. –  Henning Makholm Mar 27 '13 at 14:56
1  
@JoeZeng: True enough, this doesn't generalize to more locks. I was using parities merely as a shorthand for those two particular sets of permutations in the $n=3$ case. Sorry that wasn't clear. The point is that the difference between two successive non-wasted tries must be a derangement of the keys, and $S_3$ splits into two orbits under derangements, and the orbits happen to be exactly the odd and even permutations. –  Henning Makholm Mar 27 '13 at 15:37

1 Answer 1

up vote 4 down vote accepted

The key facet of this problem is that to be sure that you've opened all three locks, you need to find a combination of completely wrong keys (a derangement), and then a combination of completely correct keys (the correct arrangement). This will close all the locks, and then open them all again.

Suppose that the locks are A, B, C, and the keys are 1, 2, 3.

First, insert the keys matching 1A 2B 3C. If the correct combination is either 2A 3B 1C or 3A 1B 2C, then this will close all the locks. If the correct combination is 1A 2B 3C, this will flip the position of all the locks, and you cannot be sure that the lock will open due to that. However, you will be sure that inserting either 2A 3B 1C or 3A 1B 2C will close all the locks.

Then, insert the key patterns 2A 3B 1C and 3A 1B 2C, as above. If the correct combination was either 2A 3B 1C or 3A 1B 2C, then inserting 1A 2B 3C will have closed all the locks (and 2A 3B 1C will have also closed them in the case of 3A 1B 2C), and flipping them from this closed state will open the safe. If the correct combination was 1A 2B 3C, then these two key inserts will have closed all the locks, and repeating 1A 2B 3C for the fourth trial will flip all three locks and open the safe.

If the correct combination is any of the other three (1A 3B 2C, 2A 1B 3C, 3A 2B 1C), then two locks will close and one will flip. This is no good, so we need another round of four trials for these cases.

Insert the key patterns 1A 3B 2C, 2A 1B 3C, 3A 2B 1C, 1A 3B 2C in that order. The reasoning is the same as in the first case.

This solution requires a maximum of 8 trials, as both mau and ferson2020 came up with.


According to HenningMakholm in the comments below, any cycle of derangements will work. However, for the case of 3 locks, there are two separate cycles of derangements, meaning that we need $3! + 2 = 8$ total trials (because there must always be one extra trial per cycle).

In the case of 4 or more locks, there is a cycle of derangements that covers all the permutations, which means that the total number of required trials becomes $4! + 1 = 25$, or $n! + 1$ in general.

share|improve this answer
    
Very nice. I believe this generalises to $n$ locks with $n$ keys requiring $(n + 1)(n - 1)!$ maximum tries. –  ferson2020 Mar 27 '13 at 15:00
    
(did you note that this solution exploits the fact that permutations of (1,2,3) are either cyclic or anti-cyclic? The puzzle may be solved also when there are more locks, but the solution I found is ugly. –  mau Mar 27 '13 at 15:17
    
@ferson2020: You are correct. See the addendum. –  Joe Z. Mar 27 '13 at 15:24
1  
@ferson2020: No you don't need extra inserts when there are at least 4 locks; then the graph of permutations connected by derangements is well-connected enough to have a Hamiltonian path, and $n!+1$ tries will suffice (the first one is always wasted). For example for $n=4$ one could start by wasting CDBA and follow through with: ABCD, CDAB, BACD, CDBA, DCAB, ABDC, DCAB, BADC, CBAD, ... ADBC, CADB, ..., DBCA –  Henning Makholm Mar 27 '13 at 15:47
3  
@JoeZeng: No, all that is needed is that each combination we try is related to the previous one by a derangement. Then when we hit the right one, the one we tried just before was completely different and will have closed everything. We don't need to to consider what happened earlier. (Note that my solution doesn't follow CDBA by CBAD). –  Henning Makholm Mar 27 '13 at 16:04

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.