Locks and Keys
Ten people own a house. They want to put a number of locks on the
door of the house and give each person the key to a subset of locks so
that each subset of three people together have the keys to open all of
the locks, but no two people are able to open all of the locks (The key
of each lock can be given to more than one person). At least how many
locks are required to satisfy the above criteria?
Link to the problem on Twitter: https://twitter.com/Riazi_Cafe/status/1669675410966151168
The answer is equal to 45.
For every two people, there should be a special lock for them whose key
is not given to them and that all other eight people have the key to
that lock. Therefore at least \(\binom{10}{2}
= 45\) locks are needed. On the other hand, if we put a lock on
the door for every two people and give its key to the other eight
people, both conditions of the question will be satisfied.
Link to the solution on Twitter: https://twitter.com/Riazi_Cafe/status/1670370832151990272