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

Question

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.

Answer 1

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