Treasure and Locks
Thirteen pirates put their treasure in a chest. They want the chest to be openable whenever a majority of them (7 or more) agree, but not when only a minority (6 or fewer) are present. Since they don’t trust each other, they consult a locksmith to craft such a locking mechanism.
The locksmith says such a mechanism isn't possible, but he offers an alternative solution. He locks a number of padlocks on the chest such that every lock must be unlocked to open the chest. He then distributes the keys amongst the pirates. A lock can have multiple keys that open it, but each key can only open the lock it's made for.
How can they do this, and what is the minimum number of locks needed?
Hint
Think about what happens when a lock blocks a group of pirates from opening it. A group fails to open the chest if there is at least one lock for which nobody in the group has a key.
Solution
For every possible subset of 7 pirates, assign them a lock and give each pirate a key to that lock. This requires (613)=1716 locks.
To prove that this solution works, we need to show 2 things:
- For every set of only 6 or less pirates, they cannot open the chest.
- For every set of 7 or more pirates, they can open the chest.
For every set of only 6 or less pirates, they cannot open the chest.
Let's consider an arbitrary group of 6 or less pirates. Then there must be at least 7 pirates not in this group. Since there exists a unique lock for every possible subset of 7 pirates, this lock would keep those 6 pirates out.
For every set of 7 or more pirates, they can open the chest.
Let's consider an arbitrary group of 7 or more pirates. We want to show that they can open the chest.
Proof by contradiction: let's assume otherwise, that these pirates cannot open the chest. This means there exists a lock that exists on the chest whose key isn't given to any of the 7 pirates, i.e. the keys must have been given to at most 6 of the remaining pirates not in the group. However, we know that every lock has been given to 7 pirates, leading to a contradiction.
Thus, these 7 pirates can open the chest.
Try These Next
Traversing the Hypercube
Ossarion-429 is a multi-dimensional being travelling across hypercubes of various dimensions. Bored and having nothing else to do, he wonders to himself if...
Covering a Chessboard 1
You’re given an 8x8 chessboard with 2 opposite corner tiles removed. You can place dominoes on the board, with each one covering exactly 2 adjacent tiles (you...
Equal Shape Cutting 2
Cut the L-shape into 4 equal shapes of itself. The shapes can be rotated, but all 4 must be of the same size.