Morgado's old challenge

Probability Level 5

There are many locks and 9 people. At least 5 people are needed to open all the locks. If the number of locks is small as possible, how many keys does each person have?

Details and Assumptions

  • Each lock needs a different key.
  • Each key has many copies.
  • Every group of 5 people is able to open all the locks
  • This question is in memory of the mathematician Augusto C. O. Morgado.


The answer is 70.

View wiki
Felipe Hofmann by Felipe Hofmann , 24, Brazil

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Each 4 cannot open all the locks. So for every four people that we choose there is one key missing. All the other people out of this group should have this key.

So ( 9 4 ) ∗ 5 \binom{9}{4}*5 keys are needed. Since the number of locks are minimum under the above condition each 5 can open all the doors and each 4 can't.

So each person must have ( 9 4 ) ∗ 5 / 9 \binom{9}{4}*5/9 = 70 keys.

5 Helpful 0 Interesting 0 Brilliant 0 Confused

I almost understand your solution but something is missed in my mind. Please answer this questions:

Why 9C4*5 keys are needed? Can you explain more? And why It is divided by 9? So how many locks they have to open?

Hafizh Ahsan Permana - 6 years, 10 months ago

why is it divided by 9 ?

manjari singal - 6 years, 10 months ago
Yash Karnik
Apr 25, 2015

The answer is 8C4. Consider a particular person 'X'. All the groups of 4 persons from the remaining 8 guys should fall short of at least one key, and all those keys should be with Mr. X. As number of locks is minimum, they fall short of exactly one key, and hence the answer 8C4

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Julio Fonseca
Aug 3, 2014

Write a solution. each person has a key to open, together with the other ones four, therefore the key number is 8C4

0 Helpful 0 Interesting 0 Brilliant 0 Confused

give me some more explaination..??

Rahul Jain - 6 years, 10 months ago

Write a comment or ask aIn the minimum condition, it lacks a lock exactly to be open, in a group of four people, this way anybody out of the group of the four they have the key that lacks, this way the person X has a number of keys same to the number of subsets of 4 people to which she doesn't belong question...

julio fonseca - 6 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...