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 are 8 crew members, The leading member wants that only a crew of 5 people or more could open a safe he bought, To each member he gave equal amount of keys, and locked the safe with several locks.

What's the minimal number of locks he should put:

  1. at least 5 crew members would be required to open the safe?
  2. Any team of 5 crew members could open the safe, but none of the 4 team crew members.

1,2 stands individually of course.

share|improve this question
    
Can any key open any lock? Can each lock have multiple keys? Can a key open different types of locks? –  Ian Coley Mar 26 '13 at 19:11
    
I suspect each person can open some subset of the locks, essentially. It's not clear if the "leading member" is counted in the crew, but I'm assuming he is. –  Thomas Andrews Mar 26 '13 at 19:13
    
What's the common source of this kind of problems? math.stackexchange.com/questions/323694/how-many-keys-and-locks –  Andreas Caranti Mar 26 '13 at 19:19
    
I think we may not be able to give a 'minimal number'. For instance, if we give each crew member one key and put 5 locks on the door, then we're done. But that's not gonna be the best way to think about it. –  Ian Coley Mar 26 '13 at 19:20
    
Well, key is suited into an individual lock. Thing is, You can copy a key and send it to different key members. –  StationaryTraveller Mar 26 '13 at 19:24

2 Answers 2

up vote 2 down vote accepted

Consider the general case that $n$ people know certain secrets such that no subset of $k$ of them know all secrets, but any subset of $k+1$ of them do know all secrets. (Here $n=8$, $k=4$, secrets are locks, and knowing a secret is having a key.)

This can be done using $\binom nk$ secrets, each labelled by a different subset of $k$ among the $n$ people, which is the set of people that does not get to know that secret (everyone else does). Then for any subset of $k$ people the corresponding secret will not be known by them, but for any set of $k+1$ people and any secret there is at least one of them who knowns the secret.

To show one cannot do with less secrets, consider any solution to this problem, and the relation between on one hand the $\binom nk$ subsets of $k$ people and on the other hand the secrets, defined by none of those people knowing the secret. This relation is "one to at least one": it is required that any set of $k$ people not know at least one secret, and if two different subsets of $k$ people do not know the same secret, then the union of those subsets, which contains at least $k+1$ people would not know that secret, and hence not all secrets, which is against the requirement. The relation is in fact a surjective map from secrets to $k$-subsets, so there are al least $\binom nk$ secrets.

share|improve this answer
    
Thanks, Nice clarification . –  StationaryTraveller Mar 27 '13 at 10:24

This can easily be generalized, replacing 8 and 4 with a variable each.

Let the set of keys (and locks) be denoted by $K$. Let the set of keys that crew member $i$ doesn't receive be $K_i$.

For distinct indices, Condition 1 states that $K_{ijkl} = K_i \cap K_j \cap K_k \cap K_l \neq \emptyset$ (no 4 crew can open the safe), and condition 2 states that $K_i \cap K_j \cap K_k \cap K_l \cap K_m = \emptyset$ (any 5 crew can open the safe).

Claim: $ K_{ijkl} \cap K_{i'j'k'l'} = \emptyset$ for distinct quadruple sets.

Proof: Suppose not. Then $\{i, j, k, l, i', j', k', l'\}$ is a set with at least 5 distinct elements, contradicting condition 2. $_\square$

Hence, there must be at least $8 \choose 4$ locks.

Claim. $8 \choose 4$ is sufficient.

Proof: Label each of the locks with a distinct quadruple from 1 to 8. To each crew member, give him the key to the lock, if it doesn't have his number on it. Then, any 4 crew members $i, j, k, l$ will not be able to open lock $\{i, j, k, l\}$. Any 5 crew members will be able to open all locks.

share|improve this answer
    
Thank you, Nice answer. –  StationaryTraveller Mar 27 '13 at 10:23

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.