0
$\begingroup$

5 persons own a safe with a number of locks (arranged parallel, i.e. all locks must be opened to open the safe). One lock can have any number of keys. The owners want any combination of (a minimum of) 3 persons to be able to open the safe.

I can see that one solution is to have 5!/(3!2!)=10 locks and distribute the keys according to the permutations owners. But is that also the minimum number of locks?

Edit: following new searches using the work "lock" I see that the question might be a duplicate. I see also that my own solution may be wrong according to a comment

$\endgroup$

marked as duplicate by Gerry Myerson, Arnaud D., hardmath, SBareS, Daniel W. Farlow Mar 12 '17 at 18:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I don't understand your reasoning at all. Please elaborate. For example if you have 4 people and at least 3 are required to open the safe, then you would claim that $\binom{4}{3}$ locks are enough, but I can prove that it is impossible. $\endgroup$ – user21820 Jun 8 '15 at 9:13
  • $\begingroup$ I also think 10 locks are needed. $\endgroup$ – Keith Jun 8 '15 at 9:21
  • $\begingroup$ Just to clarify, it's a requirement that two people acting alone can never open the safe, right? $\endgroup$ – Keith Jun 8 '15 at 9:21
  • $\begingroup$ @Keith: yes - 3 is a minimum. $\endgroup$ – Mikael Jensen Jun 8 '15 at 9:26
  • $\begingroup$ @user21820: I would say for persons a,b,c and d, and key K1 to lock 1 etc, that a and b have both K1 and K2 and b and c have both K1 and K3. $\endgroup$ – Mikael Jensen Jun 8 '15 at 9:26
0
$\begingroup$

Yes, ten locks is the minimum number.

Given any group of two people, say A and B, they can't open the safe. That means there's some lock that only people among C, D and E have the key to. But in fact, all of C, D and E must have the key: if, for instance, C didn't have the key, then it would be impossible for A, B and C to open the safe working together.

It follows that for every group of three people, there must be a lock for which they are the key owners.

Therefore it takes $\binom{5}{3} = 10$ locks.

Edit: Conversely, we obtain a solution by having one lock for each set of three people.

$\endgroup$
  • $\begingroup$ I don't agree. Unless you show a particular way of distributing the keys, you cannot claim that there is a solution using 10 locks. $\endgroup$ – user21820 Jun 8 '15 at 9:33
  • $\begingroup$ @user21820 I hope the edit is satisfactory. $\endgroup$ – Keith Jun 8 '15 at 9:38
  • $\begingroup$ Huh your edit doesn't make sense. You need to show that any group of 3 people have the keys to all the locks. $\endgroup$ – user21820 Jun 8 '15 at 9:38
  • $\begingroup$ @user21820: I agree that Keith's edit doesn't help. But in fact $10$ locks is enough, because if $A$ and $B$ don't have a key to lock $K$, then $C, D$, and $E$ must all have it. $\endgroup$ – TonyK Jun 8 '15 at 9:41
  • $\begingroup$ Yes, that's the case. Given a group of three people trying to open the safe, and any particular lock, one of the three people must be among those who have the key. There are three people who have the key, there are three people present, and there are only five people in all, so there must be someone in common between those who are present and those who have the key. This argument for sufficiency was not repeated because the same information was implicit in the necessity argument. @user21820 $\endgroup$ – Keith Jun 8 '15 at 9:41
1
$\begingroup$

Any group of two people should not be able to open the safe, it means that for each of the $\binom 52$ groups of two, there must be at least one key they don't own. This key must be different for any two groups of two. The minimal solution is then $\binom 52=10$. For each of the 10 groups of two, there is a key they don't possess.

$\endgroup$
1
$\begingroup$

Each group of 2 should have one unique unopenable lock, so minimum # of locks needed =${5\choose 2}$= 10

"I" must have the missing key for each group of 2 to which I don't belong, i.e. ${4\choose2}$ = 6 keys, so minimum # of keys needed = 5*6 = 30

$\endgroup$
0
$\begingroup$

This question has been already answered in full, but since a commenter asked for an explicit solution, I will post one:

A     456789
B  123   789
C 0 23 56  9
D 01 34 6 8
E 012 45 7

Persons are named A-E, locks are numbered 0-9, and, for instance, C 0 23 56 9 means that person $C$ has a key for each of the locks in $\{0,2,3,5,6,9\}$.

It is easy to see that it’s minimal: there are three keys for each lock (arranged in columns), and if you remove one of those 30 keys, there will be a column with three spaces, and the group of three persons identified by these spaces will not be able to open the corresponding lock. If you remove one whole column, the two people identified by the spaces in the removed column will be able to open all remaining 9 locks.

$\endgroup$

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