# Doubts in set based solution of $5$ persons & locks problem

In the book by K.D.Joshi, titled 'Foundations of Discrete Math.', there is given on page#66, a set theoretic approach to solving the problem of 'five persons & a set of locks problem'. I have my earlier post that concerned the material on page #66, here. However, the complete soln. is presented on page#92. Have restated the material on both the pages below, with reference to page numbers for each page's material. My $7$ doubts are stated in italics wherever they occur. Also, the problem statement is given in the book on page #17.:

[contents of page #66]:
The problem condition is : there are a set of $5$ key-sets $L_i$ that are possessed by the corresponding person $p_i$. No fewer than any $3$ persons are required to open the box, to enable a quorum as a security measure. Logically it means that union of any three of these five subsets be the whole set $L$, while the union of any two should not be the whole set $L$. (So, there is a set of keys with a person, & at least $5$ persons are needed to open the lock.)

The book further states the problem soln. in terms of set-theoretic approach by taking complements of the key-sets $L_i$ by using the the De-Morgan laws as follows:
For each $i$, let $M_i$ be the complement of $L_i$ in $L$, (so $M_i$ acts as anti-key-set for a given person, i.e. what keys are not in possession of person $p_i$.).
Then the problem is to find suitable set $L$ & some subsets $M_1, M_2,\cdots, M_5$ of $L$ s.t.
(i) for any $i$ and $j$, $M_i ∩ M_j\ne 0$,
(ii) for any three distinct $i,j,k, M_i ∩ M_j ∩ M_k = 0$.

[contents of page #92]:
Thus for every (unordered) pair $\{i,j\}$ of distinct indices there must be at least one element, say $x_{i,j}$ in $M_i ∩ M_j$. (So, pairs $x_{i,j}$ should be able to open the lock.) There are $10$ such pairs by Theorem 2.18, because $\binom{5}{2} = 10$. Now, if we take two distinct un-ordered pairs say ${i,j}$ & ${p,q}$, then out of four indices at least three are distinct.

This can be seen easily as the $10$ combinations of selecting $2$ items from $5$ items (let, $a,b,c,d,e$) are as follows:
(As specifies un-ordered pairs, so using the $\{,\}$ (set) notn. to denote 2-selections)
$\{a,b\}, \{a,c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{b,d\}, \{b,e\}, \{c,d\}, \{c,e\}, \{d,e\}$,
Taking pair of such $2$ selections, with taking the first as having indices ${i,j}$ & the second as having the indices ${p,q}$, then get $\binom{10}{2} = 45$ pairings. Taking a small sample to illustrate.
(Q.1. Have no theoretical way for the same, & request some clue for that.) :
1 . $\{a,b\}, \{a,c\}$,
2. $\{a,b\}, \{c,d\}$,
3. $\{a,c\}, \{a,d\}$,
4. $\{a,b\}, \{b,c\}$,
5. $\{a,d\}, \{b,d\}$,
Here, at least $3$ indices are distinct.

Thus $x_{i,j}$ cannot be equal to $x_{p,q}$, for otherwise it will be common to at least three of the subsets $M_1\cdots M_5$.

(Q.2. Cannot figure out the above line. I tried to take a small example with $x_{i,j} = x_{p,q}$ with $i=1, j=2, p=1, q=2$, but made no sense to me.)

Thus $L$ contains at least $10$ distinct elements, one corresponding to each pair of indices. This puts a lower bound on the number of locks needed.
(Q.3. Why $10$ is a lower bound? Does the author mean the permutations of $2$ from $5$, as a combination of more than two : $M_i\cap M_j\cap M_k = \emptyset$.)
We now show that an exact bound of $10$ locks is indeed possible. Indeed, let $L = x_{i,j}: 1\le i\le 5, 1\le j\le 5, i\ne j$; where $x_{i,j}$ & $x_{j,i}$ are the same element. Now for each $i=1,2,\cdots, 5$ let $M_i =\{x_{i,j}: 1\le i\le 5; i\ne j\}$. Then for any $i\ne j, M_i ∩ M_j = \{x_{i,j}\}\ne \emptyset$; while for any three distinct $i,j,k, M_i ∩ M_j ∩ M_k = \emptyset$.

To translate the arrived solution (in terms of complements $M_i$) back in the original language in which the problem was stated, we get:
$M_i$ is the set of locks that a person $p_i$ cannot open. Each $M_i$ has $4$ elements.
(Q.4. I feel this line confuses a lot, as $M_i$ is not a set of locks, but a set of keys which $p_i$ cannot possess. So, $M_i$ = Total no. of keys - (the keys possessed by $p_i$))
(Q.5. How the value of each $M_i=4$, is not clear to me.)

So, each person can open $6$ locks.
(Q.6. How can each person open $6$ locks, when there is only one lock.)

The distribution of locks to each person can be succinctly given as follows:
For every pair of persons $p_i, p_j, x_{i,j}$ is a lock that neither of them can open, but everybody else can. (So, eliminating for $x_{i,j}$ the two persons, get $5-2=3$) So, each lock has $3$ keys.
In summary, there are $10$ keys, 3 keys to each lock, & each person has $6$ keys.
(Q.7. How can each person have $6$ keys, yet a total of $10$ keys.)

Q 1. We have $\{ a, b\} \ne \{ c, d\}$. Suppose there are only $2$ distinct indices, then the two sets are equal. Hence there must be at least $3$.

Q 2. If $x_{ij}= x_{pq}$, then we have $x_{ij} \in M_i \cap M_j \cap M_p \cap M_q$, but we know that at least $3$ of $i$, $j$, $p$, $q$ are distinct. then $x_{ij} \in \emptyset.$

Q 3. We know $x_{ij}$ exists and there are $\binom52=10$ of them and none of them overlap, i.e. they are all distinct. Since they are a subset of $L$, we have found $10$ elements of $L$. That is there are at least $10$ keys.

Q 4. $|M_i |=|L|-|L_i|$, here $|M_i|=4$, $|L|=10$, $|L_i|=6$. Note that $L$ is a set, it ignores multiplicity of duplicates.

Q 5. $M_i = \{ x_{ij}: 1 \le \color{red}j \le 5, i \ne j\}$.

Well, $j$ takes values from $1$ to $5$ as long as it is not equal to $i$, hence $|M_i|=4$.

Q 6, 7. There are $10$ locks, each has their corresponding key. The key can be duplicated and be given to multiple people. Each person has keys to $6$ of them.

import numpy as np
def combinations_of_2(l):
for i, j in zip(*np.triu_indices(len(l), 1)):
yield l[i], l[j]

c = list(combinations_of_2(range(5)))
A = np.ones((5, 10), np.int8)
for j in range(10):
for i in c[j]:
A[i][j] = 0

for i in range(5):
print(A[i])


produces the key distribution

[0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 0, 0, 0, 1, 1, 1]
[1, 0, 1, 1, 0, 1, 1, 0, 0, 1]
[1, 1, 0, 1, 1, 0, 1, 0, 1, 0]
[1, 1, 1, 0, 1, 1, 0, 1, 0, 0]


where each row indicates keys own by a person.