Locks and keys for a majority of five

Question

Five people want to keep a document in a safe fitted with several locks. Every lock must be opened to open the safe, each lock can have several copies of its key, and each key opens only its own lock.

They want: any three of the five can open the safe together, but no two of them can.

What is the smallest number of locks needed, and how many keys must each person carry?

Accepted Answer

Ten locks, and each person carries six keys. A lock for every pair. Take any two people, say A and B. They must be unable to open the safe, so there must be at least one lock for which neither A nor B has a key. Give that lock's key to the other three people, C, D and E. Call this "the lock for the pair AB". Different pairs need different locks. Could the lock for pair AB also serve as the lock for pair AC? Its keys are held by C, D, E. But then C has a key, so the lock does not block the pair AC. In general the lock that blocks a pair is held by exactly the other three people, and it blocks …

Locks and keys for a majority of five

Your answer

Discussion

Learn the concepts

Related questions