In article <3gc6ad$7el@babyblue.cs.yale.edu> of rec.puzzles, David Moews <dmoews@fastmail.fm> wrote:

[...deleted...]

Assuming that (i) each lock is locked and unlocked by one key, of which there can be any number of copies, and that (ii) all locks need to be unlocked to open the box, the answer is: Use one lock for each 7-person subset of the board, keys for each lock being given to all people in its subset. This uses C(12,7)=792 locks and 792*7=5544 keys.

Why is this minimum? If there was a lock for which 6 or fewer people had keys, the 6 or more people left over would be unable to open the box, which is unacceptable; so all locks must share their keys among 7 or more people. Now if there was some 7-person group that was not the set of key owners for a lock, the group consisting of the remaining 5 people would be able to open the box, since it shares at least one person with every other 7-person group, and every group with 8 people or more. Hence every 7-person group must be the set of key owners for some lock, which means that any solution must use at least the locks and keys above (you can use more if you like.)

David Moews ( dmoews@fastmail.fm )

To the puzzle; to the puzzles list; to the home page