3

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.

Marc van Leeuwen
  • 115,048
mau
  • 9,774
  • (I have an answer - I hope it's not unpolite to post such a puzzle, since my answer has some nice mathematical connection) – mau Mar 27 '13 at 14:19
  • Have you tried using binary switch.? – Inceptio Mar 27 '13 at 14:22
  • When you say the safe is not open at the beginning, does that mean all three locks are closed, or only that at least one of them is closed? – ferson2020 Mar 27 '13 at 14:25
  • @ferson: the latter - I am expliciting it. – mau Mar 27 '13 at 14:29
  • @inceptio: could you please explain what you mean? – mau Mar 27 '13 at 14:30
  • @mau: There are two positions for locks, open and close. Denote close with $1$ and open with $0$ . Whenever wrong key acts, it is $1 \to 0$. – Inceptio Mar 27 '13 at 14:32
  • 1
    I have a solution that requires a maximum of 8 trials. Can anyone do better? – ferson2020 Mar 27 '13 at 14:34
  • @ferson2020: my solution requires a maximum of 8 trials too, but I could not prove it's optimal. – mau Mar 27 '13 at 14:38
  • 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? – hmakholm left over Monica 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
  • @HenningMakholm I believe there are 3 keys and 3 locks, and each key will fit in each lock, so you're trying the 3 keys in the 3 locks at once, hoping you're getting them in the right order. – ferson2020 Mar 27 '13 at 14:44
  • 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. – hmakholm left over Monica Mar 27 '13 at 14:56
  • ^ I don't think it has to do with switching parities. If you try to generalize it to 4 or more locks, you can't do it in 26 or 122 or $n! + 2$ tries. – Joe Z. Mar 27 '13 at 15:25
  • 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. – hmakholm left over Monica Mar 27 '13 at 15:37
  • @HenningMakholm True enough. – Joe Z. Mar 27 '13 at 15:39

1 Answers1

4

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.

Joe Z.
  • 6,719
  • 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 – hmakholm left over Monica Mar 27 '13 at 15:47
  • @Henning Makholm Does the $n = 4$ case generalise to $n > 4$? That is, is it always possible to iterate through the $(n - 1)!$ different equivalence classes of permutations (mod cycling) in such a way that you can pick a permutation from the previous equivalence class and one from the next where the two permutations do not overlap? – ferson2020 Mar 27 '13 at 15:54
  • @HenningMakholm: The problem is that a Hamiltonian path between derangements isn't good enough; you need a bunch of complete graphs. – Joe Z. Mar 27 '13 at 15:57
  • In your example, starting with CDBA (if it's correct) and trying CBAD will flip one and close three. We can't have that. The solution banks on the fact that any permutation in a cycle will always either close all or flip all if the correct permutation is in that cycle. – Joe Z. Mar 27 '13 at 15:59
  • @ferson2020: I would strongly expect to; otherwise we'd have a construction for a new vertex-transitive non-Hamiltonian graph, of which only 5 are known. – hmakholm left over Monica Mar 27 '13 at 16:02
  • 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). – hmakholm left over Monica Mar 27 '13 at 16:04
  • @HenningMakholm That's also what I thought at first; but then I was skeptical. – Joe Z. Mar 27 '13 at 16:06
  • Your argument seems to be right, though. – Joe Z. Mar 27 '13 at 16:06