Thread: Math Q&A Game
View Single Post
StatusX
StatusX is offline
#191
Oct26-08, 07:45 PM
HW Helper
P: 2,566
Here's the proof, if anyone's interested:

Spoiler

Pick some group of M-1 people. This group must be missing the key to at least one lock. But since the addition of anyone else gives them the necessary M people, anyone outside the group must have the keys to all their missing locks. In particular, each person either has all or none of the keys to this set of locks, so if there's more than one, we might as well consolidate them into a single lock.

Thus we have a map from the set of M-1 person subsets (a set with N choose M-1 elements) to the set of locks. We show it's a bijection. If it wasn't injective, and two M-1 person subsets were missing the same lock, then their union, a group of at least M people, would also be missing the lock, a contradiction. If it wasn't surjective, there would be locks that no M-1 person group is missing, but then we clearly don't need these locks.

Thus an optimal solution has N choose M-1 locks, with one lock for each M-1 person group, and with the people in the group being precisely the people who don't have the key to the corresponding lock.