Math Help - Combinations with Keys and Locks

[GTM]

We did this example in class but I don't understand it.

11 mad scientists working on a solution to global warming, put their research into a safe. They want to lock the safe so that at least 6 scientists are needed to be present to open the box.
a) What is the minimum # of locks needed for the safe?
b) What is the minimum # of keys each scientists needs?

Answer: a) When picking groups of 5, there should be 1 lock not opened. For every two groups of 5, this lock has to be different.
number of locks <-> groups of 5
C(11,5)

b) # of keys / scientist <-> C(10,5)

That was what we did in class.

I think I understand a). It was because thats the # of ways to pick 5 people. Each way corresponds to 1 unopened lock.

I don't get b...

EDIT: And yes, it should be "at least 6 scientists need to be there, but only 6 is necessary."

[Syrin]

If you choose one scientist out of the bunch of 11, there are 10 left. How many different groups of 5 scientists (to sum up to six with the first one we chose) can you select from the 10 remaining scientists? There will need to be a different key for each such group (as stated in the question), so the number of requisite keys per scientist must then be 10 choose 5.

[GTM]

Still sort of not following >_>

[Syrin]

Okay, uh.

Every single group of 6 scientists is both necessary and sufficient to open the safe. You cannot have less than 6, you do not need more. Choose an arbitrary scientist from the group, A. There are now 10 scientists left.

To form the requisit 6-person group, we must choose 5 more scientists from the remaining 10. There are C(10,5) such unique possible ways of choosing the 5 scientists. There has to be a unique key for each such group for, if there were not, then two groups would have an identical key, which would imply that you don't need 6 scientists.

So for this arbitrary scientist A, there are C(10,5) unique keys that he must hold in order to be able to order the safe for any of the possible configurations he might find himself in.

[phlip]

As you say for part a, if you have a group of 5 people, there has to be some lock they aren't able to open... and this lock has to be different for each group of 5 people, as if there were two different groups of 5 people that couldn't open the same lock, then their union (which would have to have at least 6 people) wouldn't be able to open the lock... but every group of 6 needs to be able to open the safe. So there needs to be at least one lock for each group of 5 people.

Now, similarly, for each group of 5 people, we have a unique lock that that group can't open. Every other person has to have a key to that lock... so that any group of 6 that included that original 5 would be able to open that lock. So every one of those C(11,5) locks must have 6 keys, so there's at least 6*C(11,5) keys in total. These will be evenly distributed over the scientists (there's one for each group of 5 people, given to everyone not in that group, and each scientist is in the same number of groups) so the number of keys per scientist is 6*C(11,5)/11. With a bit of manipulation of the factorial definition of C(n,r), we can show that's equal to C(10,5) (indeed, in general, r*C(n,r-1)/n = C(n-1,r-1), which is exactly the result you'd get for n total scientists, where a group of r can open the safe).

Alternatively (and this is the way that Syrin was explaining it): as I just mentioned, each scientist has a key for each 5-person group they're not a member of, as that's the key they'd be needed for if they were to join that group, bringing the count up to 6. And the key that each of those groups of 5 is missing must be different for each group. So each person must hold as many keys as there are groups of 5 in the remaining 10 people... that is, C(10,5).

[squareroot1]

Jeez, it's hard enough getting a mad scientist to maintain a working death ray, much less keeping track of 252 keys.

Imagine the process of 6 of them trying to unlock the safe with the 2772 locks....

[{delta}]

They are going to feel silly after it sinks in that they found a solution to global warming, but failed at devising a better locking system.

[mike-l]

Jeez, it's hard enough getting a mad scientist to maintain a working death ray, much less keeping track of 252 keys.

Imagine the process of 6 of them trying to unlock the safe with the 2772 locks....

Maybe that's how they became mad in the first place?

[GTM]

Thanks, Syrin. That explained it a lot better.

And phlip, thats a very good explanation too. Thanks.

[BlackSails]

The minimum number of locks is 1 and keys per scientist is 1. You just make a complicated lock that will only open if at least 6 people use their keys at once.

They have things like that for launching nuclear missiles (it requires 2 keys)