Another puzzle with locks

Question

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.

Answer 1

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.