Six scientists are working on a secret project. They wish to lock up the documents in a cabinet so that the cabinet can be opened when and only when three or more of the scientists are present. What is the smallest number of locks needed? What is the smallest number of keys each scientist must carry?
I am thinking of solving this problem is this way: Suppose there are n locks and label the keys with 1,2,...,n.
Let $X=\{1,2,...,n\}$. We have to construct six non-empty subsets of $X$, say, $A_1,A_2,...,A_6$ such that
- $A_i \cup A_j \cup A_k = X$ for distinct $i,j,k$;and
- $A_i \cup A_j \ne X$ for $i \ne j$.
From here I don't know how to proceed. Any help will be much appreciated!
Best regards,Michael.
Building on lulu's hint :
For each couple of scientists, there must be a lock they don't have the key for and every other scientists got the key.
How many $c$ couples of scientists can we pick with a group of $6$ scientists ?
$$ c = {6\choose 2} = {6!\over 2!\cdot 4!} = 15$$
So the minimum number of locks is $15$.
From there you just have to pick every single couples of scientists and give a key to the $4$ other scientists.
Here is an example of what is might look like :
First step : we consider the couple $(\text{scientist }1,\text{scientist }2)$ and give the key to lock $1$ to every other scientists. Then we repeat for the couple $(\text{scientist }1,\text{scientist }3)$ and so on ...
You can check that every couple of scientists is always missing a single key and that every other scientists got that key.