## Math Help - Combinations with Keys and Locks

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

### Math Help - Combinations with Keys and Locks

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."
GTM

Posts: 57
Joined: Tue Nov 10, 2009 4:53 am UTC

### Re: Math Help - Combinations with Keys and Locks

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.
Syrin

Posts: 291
Joined: Thu May 24, 2007 7:10 pm UTC

### Re: Math Help - Combinations with Keys and Locks

Still sort of not following >_>
GTM

Posts: 57
Joined: Tue Nov 10, 2009 4:53 am UTC

### Re: Math Help - Combinations with Keys and Locks

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.
Syrin

Posts: 291
Joined: Thu May 24, 2007 7:10 pm UTC

### Re: Math Help - Combinations with Keys and Locks

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).
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6731
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Math Help - Combinations with Keys and Locks

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....

squareroot1

Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

### Re: Math Help - Combinations with Keys and Locks

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.

{delta}

Posts: 53
Joined: Sun Apr 12, 2009 9:32 am UTC

### Re: Math Help - Combinations with Keys and Locks

squareroot1 wrote: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?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2512
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Math Help - Combinations with Keys and Locks

Thanks, Syrin. That explained it a lot better.

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

Posts: 57
Joined: Tue Nov 10, 2009 4:53 am UTC

### Re: Math Help - Combinations with Keys and Locks

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)

BlackSails

Posts: 5128
Joined: Thu Dec 20, 2007 5:48 am UTC