# Distributing locks and keys so certain subsets of people can open all locks

A vault can be opened by n number of keys. Five people, A, B, C, D, E are given some of the keys. Each key can be duplicated arbitrary number of times. Find the smallest number n and the distribution of the keys per person so the vault can be opened if and only if one of the following situations happened:

• persons A and B are present together

• persons A,C and D are present together

• persons B,D and E are present together

Any ideas how this problem can be aprroached? I've tried with truth tables and Veicth diagrams but I only find my self going in a circle.

• – Mike Earnest Apr 17 at 21:36

The following logical statement determines which groups of people should be able to open the vault: $$(A\wedge B)\vee (A\wedge C\wedge D)\vee (B\wedge D\wedge E)$$ This is in conjunctive normal form. If we convert this to disjunctive normal form, then we will have a list of clauses of the form $$(X\vee Y\vee Z\vee \dots)$$ which all must be simultaneously satisfied. But this corresponds exactly to a lock distribution solution. Each clause represents a lock, and all locks must be opened. The variables comprising each clause represent who is given a key to that lock, and at least one person with that key must be present.

So, we just need to convert that CNF to a DNF. This is a purely mechanical process, which is found by fully distributing about the CNF ($$\vee$$ distributes over $$\wedge$$), then eliminating redundant clauses. I made such a converter, available here, and the result is $$(A \vee B) \wedge (A \vee D) \wedge (A \vee E) \wedge (B \vee C) \wedge (B \vee D)$$ This means that $$5$$ locks is optimal (since there are five clauses), and the key distribution is

Lock 1:  A, B
Lock 2:  A, D
Lock 3:  A, E
Lock 4:  B, C
Lock 5:  B, D

• Thanks a lot for the answer, I understood the part about converting CNF to DNF but I didn't get the distribution of keys per person. So you're saying that there are 5 keys? How are they distributed per person? – syd Apr 17 at 23:41
• The DNF is $$(A \vee B) \wedge (A \vee D) \wedge (A \vee E) \wedge (B \vee C) \wedge (B \vee D)$$ Therefore, there are five locks. The keys to the first lock are given to $A$ and $B$, since the first clause is $(A\vee B)$. The keys to the second lock are given to $A$ and $D$, etc @syd – Mike Earnest Apr 17 at 23:48
• For the record, it seems obvious that this procedure should produce a minimal n, but I'm not sure how I would go about proving it. – Richard Rast Apr 18 at 1:33
• @RichardRast It boils down to what I was saying in that first paragraph; a lock/key solution corresponds to a DNF exactly, so the # of clauses in the DNF equals the number of locks optimally. You have to make sure the DNF has no redundant terms, of course. – Mike Earnest Apr 19 at 0:03