Category: Puzzles

Nine pirates have captured a treasure chest. In order to protect it, they decide to lock it using multiple locks and distribute several keys for each of these locks among them, so that the chest can be opened only by a majority of the pirates. What is the minimum number of keys each of the pirates should get?

First, we show that for every four pirates, there exists a lock which cannot be opened only by them and can be opened by everyone else. We choose an arbitrary group of four pirates. If they can open every lock, then they can access the treasure without the need of a majority. If any of the remaining pirates cannot open that lock, then he, together with the initial group of four still cannot access the treasure. Thus, the claim is proved and to each group of four pirates we can assign a unique lock. These are \binom{9}{4}=126 locks in total. Finally, every pirate should get keys for \binom{8}{4}=70 of these locks, one for each group of four additional pirates he can be a group of.