3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – syd Apr 17 at 23:41
  • $\begingroup$ 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 $\endgroup$ – Mike Earnest Apr 17 at 23:48
  • $\begingroup$ 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. $\endgroup$ – Richard Rast Apr 18 at 1:33
  • $\begingroup$ @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. $\endgroup$ – Mike Earnest Apr 19 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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