Math Problem (involves probability, I think at least)

[jarsoffart]

"A certain village in Jacobean times had all the valuables locked in a common town chest. The chest had a number of locks on it, each lock with a different key. The aim of the village was to ensure that any three people of the village would amongst them have enough keys to open the chest, but no two people would be able to. How many locks are required, and how many keys?"

I don't know the answer...

 

[diskop]

May involve the pidgeonhole principle also.

 

[notfred]

who really gives a sh!t? That was 1000 years ago.

 

[jarsoffart]

Isn't there some quote with the essence of "If you forget history it will repeat itself."?

 

[Novgrod]

This question asks you to assume quite a bit, but:

if we assume that each person can unlock two locks at the same time, then a chest with four locks can be unlocked by two people. A chest with five or six locks can be unlocked by three people, but not by two people. This way you can give everybody the same five or six keys, one for each lock, and three people can have at it.

This seems a little simple so I'm assuming i've missed something.

 

[Alphazero]

Originally posted by: notfred
who really gives a sh!t? That was 1000 years ago.

More like 3-4000. That's probably really important to the solution....

 

[jarsoffart]

Originally posted by: Novgrod
A chest with five or six locks can be unlocked by three people, but not by two people.

What if each person can open three locks? How can you be sure that the three have the same two keys that can only open two kinds of locks?

 

[Calundronius]

Originally posted by: Novgrod
This question asks you to assume quite a bit, but:

if we assume that each person can unlock two locks at the same time, then a chest with four locks can be unlocked by two people. A chest with five or six locks can be unlocked by three people, but not by two people. This way you can give everybody the same five or six keys, one for each lock, and three people can have at it.

This seems a little simple so I'm assuming i've missed something.

I agree that the problem isn't worded well at all. To much left up in the air.
The answer definitly involves the pigeon hole principle, and here's how I'd go about solving it:
The chest will have some number of locks. Each lock requires a specific type of key. A key for lock #3 won't unlock any of the others, for example.
All the townspeople are given some number of keys: one person may get keys for locks #1 and #4, another for #2 and #3, another for #1 and 3, and so on...they are given randomly but distributed so that no-one gets two copies of the same key.
You just have to figure out how many locks there have to be, and how many keys...I think 5 locks and 3 keys per person will do it, but I'm not sure.

But the question is so ambigious, you could say that the chest is a very complicated lock system, with a unique key for every citizen, and the locking system designed to open for any three keys. Don't ask me to design it, but it could be done.

 

[diskop]

Yeah exactly. The question is too ambiguous. We need a bit more information on the locks, how many keys a person should have, etc.

 

[jarsoffart]

I don't know the answer and that is all the information I was given, but I know that you are supposed to decide how many keys each person should have and I'm assuming that each lock can only be opened by one kind of key and each key can open only one kind of lock.

I think 5 locks and 3 keys per person will do it, but I'm not sure.

What if each of the three people had the same three keys, since the keys are given out randomly, so that only three of the five different locks on the chest can be opened? What is the pigeonhole principle by the way? hahaha... I really hope this is solvable.

 

[Soccer55]

I think the number of keys that you give to each person will be determined by the number of locks. For example, if you give each person X keys, you may need 2X locks on the chest. I agree with the others that have said that this may involve the Pigeonhole Principle.

-Tom

 

[HomeBrewerDude]

i have no idea and its friday so i am out of here.

 

[0ops]

1) This is a combinatorics, not probability question
2) It is not ambiguous nor poorly worded, you just have to read it carefully:

Each person is given a set of keys. Two people may have some keys in common but they wont have all the keys
needed to open all the locks. However, three people will (or you can pretend they are combination locks, any two
people wont know all the combinations, but any three will).

Answer Below:






























Suppose there are P people in the village. A lock is made for every possible pair of people (in other words P*(P-1)/2 locks). The key for
a lock is NOT given to either of the pair associated with the lock, but it is given to everyone else. In this way any two people
will always have a lock they can't open (but they can open all other locks) and any third person can open the lock that those two
people can't. So how many keys does each person have? He has a key for each possible pair of people that doesn't include him:
(P-1) * (P-2) / 2.

Example: There are 4 people, ABCD and so 6 keys, numbered 1,2,3,4,5,6. All possible pairs of people (and the key that they both DONT have) are:
AB 1
AC 2
AD 3
BC 4
BD 5
CD 6

So
A has keys 4,5,6
B has keys 2,3,6
C has keys 1,3,5
D has keys 1,2,4

You can check that this works.

 

[Peetoeng]

Did Jacobian time Napster-like service in which people can trade keys exist? If it did, that'd complicate the problem.

Let me try baby-step process here:

Say that,
K = number of keys (each is different) given to each citizen
L = number of locks on the town chest.

Requirement:
(1) 2K keys will not open the chest because either:
a. they don't have enough keys (<L)
b. they have > L keys but some are identical so distinct keys < L

(2) 3K keys will open the chest because:
a. they have L keys and each key is different
b. they have > L keys, some are identical keys.


What are K and L?

If we just need to satisfy 1a and 2a, the problem is trivial: 3K = L.

Distinct keys from every 3 combinatorial of (L,K) = L.

Someone picks this up...

 

[jarsoffart]

0ops is a genius!!! HE/SHE IS A MAD GENIUS!! I actually haven't checked his answer (hahaha) but it sounds good and I'm too tired. 0ops must go to Caltech, not a dumb school like Stanford and Berkeley.

 

[diskop]

Originally posted by: jarsoffart
0ops is a genius!!! HE/SHE IS A MAD GENIUS!! I actually haven't checked his answer (hahaha) but it sounds good and I'm too tired. 0ops must go to Caltech, not a dumb school like Stanford and Berkeley.

Very true. Man Berkeley Sucks(tm).

 

[cdan]

How about 3 locks with 1 key per person?