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