14
$\begingroup$

Here's an old puzzle I found in a book once.

A box has some number of locks on it. It is guarded by a Grand Vizier and four slaves, each of which hold keys to the locks.

The Grand Vizier and slaves each hold a different set of keys to the locks, and each key they hold opens a different lock.

The keys they hold are in a certain combination such that as long as the Grand Vizier is with one slave, or if any three slaves are together, they will have all the keys to open the box; but if less than that are together, they cannot. How many locks did this box have at minimum?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ are the locks keyed alike? $\endgroup$
    – ratchet freak
    May 15, 2014 at 15:05
  • $\begingroup$ No; each key opens only one of the locks. $\endgroup$
    – user88
    May 15, 2014 at 15:05
  • $\begingroup$ Define "lock." If the keys fit together properly, you could have one lock. $\endgroup$
    – Kevin
    May 15, 2014 at 15:06
  • $\begingroup$ 'Each of which holds keys' - do they hold one or more keys each ? $\endgroup$
    – Pat Dobson
    May 15, 2014 at 15:13
  • $\begingroup$ @Kevin: Each lock takes a single key. There's no combination of keys or anything like you're doing. $\endgroup$
    – user88
    May 15, 2014 at 15:22

4 Answers 4

Reset to default
15
$\begingroup$

The best solution I've found has 7 locks.

The Grand Vizier has keys 1, 2, 3, 4, 5, 6.

Slave 1 has keys 1, 2, 3, 7.

Slave 2 has keys 1, 4, 5, 7.

Slave 3 has keys 2, 4, 6, 7.

Slave 4 has keys 3, 5, 6, 7.

A couple of things simplify the deduction of this puzzle:

  • If the Grand Vizier has every key but one, and every slave has the missing key, that reduces the problem to 4 slaves and one less lock.

  • Every key must be held by at least two slaves.

The rest I just brute forced with a (digital) pencil and paper.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Oops, I was one step too late xD +1 $\endgroup$
    – Jerry
    May 15, 2014 at 15:56
  • $\begingroup$ This is the correct answer. $\endgroup$
    – user88
    May 15, 2014 at 17:16
9
$\begingroup$

The question doesn't place any constraints on the design of the box, so we can exploit that to get a 6-lock solution.

So we can either handle the two use cases with two lids, each covering half of the top of the box, or we can have one lid with a set on locks on one side and a set of locks on the other side, such that the locks on the side we're not unlocking function as the hinge.

We handle one of the two sides with a lock for which the Grand Vizier has the only key and a lock for which each of the slaves has a key.

For the other side, we use a similar technique to this one to create a bolt which can slide only if three of four locks are removed. (The technique in the photo has a bolt which is constrained to slide in one direction, but is blocked by a disc. That disc has N holes, each of which has a padlock through it, and can rotate so as to put any of the holes above the bolt. In this case we want the bolt to end in a fork such that it has three ends which must pass through holes. There is more discussion on complex lock configurations on Bruce Schneier's blog).

In fact, it should be possible to design the bolt in such a way that we can reduce this to 5 locks. We use the same forked bolt and rotating disc approach, but the Vizier's lock allows us to fold back the fork such that the bolt only needs one hole in the disc to be free.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yours solution a solution suggests two problems which are probably different from what was intended, but could be interesting in their own right: if the box could have multiple lids, but each lock could only be attached to one of them, and opening a lid required releasing all the locks attached to it, what would be the optimal solution? What if a mechanism could require arbitrary combinations of locks to open? In the latter case, a solution with one lock per slave and one for the vizier would be trivial, but if there were enough slaves I don't think it would be optimal with fixed quota of 3. $\endgroup$
    – supercat
    Jun 8, 2014 at 17:44
  • $\begingroup$ If the requirement for a general N were either vizier-plus-one, or a majority of slaves, I wonder what the minimum number of locks would be if the puzzle explicitly permitted the use of an arbitrarily-complex locking mechanism? I would think that it should be possible with large enough N for the number of locks to be below the number of participants, but I don't know at what N that would first occur? $\endgroup$
    – supercat
    Jun 8, 2014 at 17:57
  • $\begingroup$ @supercat Easy - each slave gets a wooden stick, the lock opens, if there are N wooden sticks inserted. You only need as many locks as you need slaves at once. With combination keys you would even only need one lock! $\endgroup$
    – Falco
    Aug 6, 2014 at 9:34
  • $\begingroup$ @Falco: Perhaps I should have rephrased the question: assume any particular padlock will open (and can be left open) if given a particular key, and not open otherwise, and the only factor which may determine whether the box opens is whether a suitable combination of padlocks has been unlocked, but any combination of slaves may be given keys to each padlock, and the linkage between padlocks and the box's locking mechanism may be arbitrarily complex. $\endgroup$
    – supercat
    Aug 6, 2014 at 15:20
8
$\begingroup$

Kendall Frey's answer gives an example of how to do this with 7 locks, this proves that minimum is not greater than 7.

Unfortunately, Kendall Frey's answer does not give an answer to the question what exactly is the minimum number of locks. I met a similar puzzle, and can take the honour to prove that 7 is the minimum.

To do this I need to add one more condition to the puzzle: "the locks are placed in such a way that to open the box one needs to open all locks". [According to reaction of the author (Joe Z.) to answer of Peter Taylor, that violates this condition, I can assume that this condition was meant to be in the puzzle formulation and it is ok to use it.]

The idea of the prove of minimality is to count missing keys for different combinations of people. Here we go:

  1. Each two slaves must have at least one key missing, since they are not able to open the box.

  2. This missing key must be different for each pair of slaves. Otherwise combining two pairs we will have 3 or 4 slaves with one key missing - they won't be able to open the box.

  3. Therefore we have at least as many keys as many pairs of slaves we can construct. There are ${4 \choose 2} = 4!/2!/2! = 6$ possible pairs of slaves. That means we have at least 6 different keys.

  4. Each of those keys have at least one slave, which doesn't have it. Grand Vizier can't open the box by himself, therefore he has at least one key missing. But this can't be the key some of slaves missing, otherwise he won't be able to open the box with any slave. Therefore one more key exists.

  5. Concluding, in total they must have at least 7 keys and 7 locks.

To make my answer complete I will reconstruct the possible keys distribution following my prove of minimality.

  1. There will be exactly 7 keys: 1,2,3,4,5,6,7.

  2. We have 6 pairs of slaves: (1,2); (1,3); (1,4); (2,3); (2,4); (3,4). Let's assign one key to each pair (the missing key for a pair). (1,2) must miss key 1; (1,3) must miss key-2; ... (3,4) must miss key-6.

  3. Take all pairs slave-1 belong to: (1,2); (1,3); (1,4). They must not have keys 1,2,3. So we will give slave-1 only keys 4,5,6,7. In the same way we decide, which key to give to all other slaves:

    1 - 4,5,6,7.
    2 - 2,3,6,7.
    3 - 1,3,5,7.
    4 - 1,2,4,7.

  4. The only thing that left to do is to assign missing to Grand Vizier. He will not have key-7:

    Grand Vizier - 1,2,3,4,5,6.

  5. It is easy to check that Grand Vizier with any slave can open the box, and any 3 slaves can do it.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Nice proof, although it feels like it's missing a conclusion in the form of "For $N$ slaves, you must have $n$ locks and keys." $\endgroup$
    – Bobson
    Jun 13, 2014 at 20:57
  • $\begingroup$ It doesn't. There was no such a request... Only 4 slaves. $\endgroup$
    – klm123
    Jun 13, 2014 at 21:00
  • $\begingroup$ I meant that it does all the setup to be able to provide such an generalization, but then it doesn't do so. It doesn't need it to answer the question. $\endgroup$
    – Bobson
    Jun 13, 2014 at 21:01
  • $\begingroup$ The approach taken is similar to my answer to the generalised problem. $\endgroup$
    – Peter Taylor
    Jun 14, 2014 at 7:04
  • $\begingroup$ @PeterTaylor, yes. I would say it is exactly the same. $\endgroup$
    – klm123
    Jun 14, 2014 at 7:08
3
$\begingroup$

Another variant would be a Box where you have to open all Locks at once, or where you cannot pull out a key as long as the Lock is open!

Then you would only 3 Locks, all of them can be opened with the same type of key:

The Vizir has 2 Standard Keys The Slaves each have one 1 Standard Key

If three Keys come together you open the box!

Another way, which is also kind of trickey, but won't break any of the rules:

The Box has 3 Locks: 1,2,3, The locks are attached in an even triangle, right next to each other and the locks are designed in a way, you can only remove the key when the lock is closed. As long as it is open the lock is stuck.

Each Key has a big nice cylindrical grip. So Big that you cannot put in two keys at once, if they have the same length, as their grips will hinder each other. So you can only insert 3 keys, if all 3 keys have different lengths: You insert the shortest first, then the second and the longest last.

Each slave now gets 3 Keys (one for each lock) but each slave will get a set of 3 keys which are all of the same length (Slave 1 has 3 keys of length 1, Slave 2 three keys of length 2, ...) So although each slave has a key for all 3 locks, they can only use one of them at once.

When 3 Slaves come together, they have 3 different lengths among them, so they can open the Box. The Vizir has 2 Keys: 1 and 2 with Length 5 and 6, so they can combine with a Key-3 form any Slave!

Improve this answer
$\endgroup$
3
  • $\begingroup$ I like this! This could be an interpretation of the original problem, not necessarily a variant, although the answer is a bit too close to the rule boundary: "The Grand Vizier and slaves each hold a different set of keys to the locks," $\endgroup$
    – justhalf
    Aug 5, 2014 at 1:29
  • $\begingroup$ Your question assumes that any key can open any lock, as long as there are three total. That assumption is false. $\endgroup$
    – user88
    Aug 6, 2014 at 4:03
  • $\begingroup$ @JoeZ. This is why I said a variant - The sentence "each key they hold opens a different lock" is the problem, so the Vizir cannot hold 2 keys of the same type. Without this requirement I could have two locks, which can be opened by the same key ;-) $\endgroup$
    – Falco
    Aug 6, 2014 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.