Four scientists are working on a secret project. They wish to lock up the documents in a cabinet such that the cabinet can be open if and only if 3 or more scientists are present.
a. What is the smallest number of locks needed?
b. What is the smallest number of keys that each scientist must carry?
c. Design a scheme with the minimum number of locks needed and the minimum number of keys for each scientist that will actually accomplish the desired security.
As to how many locks, for any group of 2 scientists there must be at least one lock they cannot open.
Moreover, for any two different groups of 2, the:”inoperable” lock must be different for each group.
Thus, at least C(4, 2) = 6 locks are needed.
As to how many keys, whenever scientist S is associated with a group of 2 other scientists,
scientist S must have the key to at least one lock that the other 2 scientists cannot open.
Moreover, for any two different groups of 3, the “inoperable” key must be different for each group.
Thus, at least C(3, 2) = 3 keys are needed.
Now, we must design a scheme with 6 locks and 3 keys for each scientist that will actually
accomplish the desired security. For each of the 6 groups of 2, label a lock with the two names on it.
This means that a lock has 2 names on it of those scientists who cannot open it. For each group of
2 scientists bring in a 3rd scientist. He must have the key(s) to the lock(s) that the other 2 scientists
do not have. This will meet the security requirements.
Consider the following scheme to accomplish the desired security:
Denote scientists: a, b, c, d
Denote locks: L1, L2, L3, L4, L5, L6
Labels for locks:
L6(a, b): lock 6 cannot be opened by scientists a, b
L5(a, c): lock 5 cannot be opened by scientists a, c
L4(a, d): lock 4 cannot be opened by scientists a, d
L3(b, c): lock 3 cannot be opened by scientists b, c
L2(b, d): lock 2 cannot be opened by scientists b, d
L1(c, d): lock 1 cannot be opened by scientists c, d
Labels for scientists:
a(L1, L2, L3): scientist a has keys for locks 1, 2, 3
b(L1, L4, L5): scientist b has keys for locks 1, 4, 5
c(L2, L4, L6): scientist c has keys for locks 2, 4, 6
d(L3, L5, L6): scientist d has keys for locks 3, 5, 6
Hint: Write out the possible configurations of three you can make out of the four scientists. Then assign each of them keys in a way that all the locks can be opened in each of the configurations. (The discussion below might help you decide how many locks there should be.)
I will show that it is not possible if each lock has a distinct key from other locks, and each scientist only has one key: Suppose we have scientists $A,B,C,D$.
Suppose there's one lock. Then at least one of the scientists must have a key which opens it; WLOG $A$. Then $A$ going alone can open it. So one lock is not possible.
Suppose there are two locks, 1 and 2. Then WLOG $A$ has a key to 1 and $B$ has a key to 2. Then $A$ and $B$ together can open it; again requirement not satisfied.
Suppose three locks: 1, 2, and 3. Then WLOG $A$, $B$, $C$ have keys to 1, 2, 3, respectively. We can give $D$ key 1, 2, or 3; WLOG $D$ gets 1. Then if $A$ and $D$ are in the group of three, whether they add $B$ or $C$ as the third, the three locks cannot be unlocked.
Suppose four or more locks. Then no group of three can open the door.
