0
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.