wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 13 pirates
        
(Message started by: klbarrus on Jul 25^th, 2002, 9:59pm)

Title: 13 pirates
Post by klbarrus on Jul 25^th, 2002, 9:59pm

Consider a smaller problem, locks for 3 pirates. In this case you have:

L1 = 1,2
L2 = 1,3
L3 = 2,3

where the numbers indicate which pirate can open the lock (so pirates 2 and 3 can open lock 3). In this case, any 2 pirates can open all 3 locks.

For 5 pirates, we nave

L1 = 1,2,3 L2 = 1,2,4 L3 = 1,2,5 L4 = 2,3,4
L5 = 2,3,5 L6 = 3,4,5 L7 = 1,3,4 L8 = 1,3,5
L9 = 1,4,5 L10 = 2,4,5

And any 3 pirates can open all the locks and get the treasure.

This boils down to a combination problem: how many ways to combine y items out of x.

So the answer is 7 C 13 = 13!/(7!6!) = 1716 locks needed.

Title: Re: 13 pirates
Post by Frothingslosh on Jul 25^th, 2002, 10:31pm

Boy, this is another one that depends on how you understand the wording of the puzzle:

The locksmith puts a specific number of locks on the safe such
that every lock must be opened to open the safe. Then he distributes
keys to the pirates such that every pirate has some but not all of the
keys. Any given lock can have multiple keys but any given key can
only open one lock.

If the locks are padlock types that can be removed from the safe
then you might be on to the answer, although it seems like there
should be something simpler. However, I understood the locksmith
mount locks onto the safe, like keyholes in the door. I further took
the "any given key can only open one lock" as meaning the key was
captive in the lock when it activated it and could only be removed when
that lock was in the locked position (so it couldn't be used to open
multiple locks). With this take on the problem I can solve it with
seven locks - and they can all be keyed alike! Each pirate gets one
key, seven are needed to open the safe.

Looks like my locksmith is a more skilled craftsman than yours.

Of course, it doesn't seem to belong in the hard group then, but it is
the last one in the group, and maybe the expectation that it is hard
is what makes it hard.

Title: Re: 13 pirates
Post by klbarrus on Jul 25^th, 2002, 10:55pm

Admirable, but I think you are stretching it with your assumption ;)

Any key can open one lock - I took this to mean exactly that, each key only fits one lock and no other lock. Like the door of my apartment, my key opens it and not the other doors in my building.

Plus, I can't envision a locking mechanism that opens as you describe. Imagine a door with 13 key holes, of which opening any 7 will open the door?? What about the other 6 that remain locked??

I can however imagine 10 locks (take my 5 pirate simpler problem), each with unique key. The locksmith makes 3 copies of each key and distributes them as described. All 10 locks can be opened by any combination of 3 pirates. I can imagine the chest and/or door opening when all the locks are opened!

And thus, 1716 locks needed for 7 of 13 to open, etc.

Title: Re: 13 pirates
Post by Frothingslosh on Jul 25^th, 2002, 11:29pm

Plus, I can't envision a locking mechanism that opens as you describe. Imagine
a door with 13 key holes, of which opening any 7 will open the door?? What
about the other 6 that remain locked??

You missed my point - there are not 13 locks on the safe,
just 7 keyholes, all keyed alike. A total of 7 locks. Each lock
has a dealbold that is withdrawn when the key is used, but
the key can't be taken out of the lock without returning
that deadbolt to the locked poition. All 7 locks are keyed alike
(maybe not like the building you live in, but like the front and
back door to my house, or like the doors and trunk on my car).
Any 7 pirates can open the safe. one, two, or six cannot, even
thought their keys fit all the locks.

Title: Re: 13 pirates
Post by klbarrus on Jul 26^th, 2002, 12:29am

Ah... I see what you are saying.

I guess more info is needed to disambiguate the problem. I can't believe the intent of the puzzle boils down to a trivial answer. Heck, in the trivial case, any 1 pirate can just duplicate his key 6 times and make off with the loot! ;)

Title: Re: 13 pirates
Post by srowen on Jul 26^th, 2002, 11:43am

I think klbarrus's answer is right - maybe I can offer some more detailed rationale. I'm not 100% sure there isn't an answer with fewer locks, but this sounds good.

Say there are n pirates. klbarrus proposes that the locksmith will make (n+1)/2 keys for each lock. How do you distribute the keys to each lock? Well there are n C ((n+1)/2) ways to do that (i.e. 1716 = 13 C 7, for 13 pirates), so why not make that many locks (1716), and distribute the keys to each in a different way, that is, covering every possible one of the 1716 ways you can distribute them.

Now, the real questions are:
1) Can any (n+1)/2 (7) pirates open all the locks? If so then clearly any larger majority can also.
2) Are all groups of (n-1)/2 (6) pirates unable to open the locks? If so then clearly any smaller minority is also unable to.

1 is easier to see - any given lock has (n+1)/2 (7) keys. By the pigeonhole principle, any group of (n+1)/2 (7) pirates must have one of them (e.g. if there are 7 keys distributed among 13 people, then any 7 must have at least one, since only 6 people don't have one).

2 is somewhat harder. For any 6 pirates, there must exist some lock (exactly 1, in fact) whose keys were given to the other 7 pirates. Remember that each lock's keys are distributed differently, and we have enough that every possible distribution is covered. So, any 6 will always be missing the key to 1 lock.

So 13 C 7 = 1716 definitely works... and elements of the solution make me think it is the best possible one, but I don't know how to show that yet.

Title: Re: 13 pirates
Post by Alex Harris on Jul 26^th, 2002, 11:37pm

To see why this is optimal:

For any given subset of size 6 there must be some lock which prevents that subset from opening the chest (i.e. no member of this subset has the key for the lock) otherwise that group of 6 could open the chest. If any lock prevents 2 different groups of size 6 from opening the chest, then it also prevents the union of these 2 groups from opening the lock (none of them have the key). This union must have size at least 7 since the groups are distinct and so there is some quorum who is prevented by this lock. Contradiction. So each lock can prevent at most 1 subset of size 6.

Thus you must have 1 lock per subset of size 6. More generally 1 lock per subset of size [number of pirates needed to open chest]-1.

Title: Re: 13 pirates
Post by cnmne on Jul 28^th, 2002, 5:36pm

Frothingslosh may have a really skilled locksmith, probably so good that after twelve pirates leave the 13th can get 6 copies of his key made. Which is the other reason that klbarrus has the only real answer.

If you could make keys that could not be duplicated, then there might be a better answer. Maybe the keys just activate an eye scanner :)

Title: Re: 13 pirates
Post by tim on Jul 30^th, 2002, 7:53pm

I thought both solutions were pretty trivial. Is there a way to interpret the problem that would actually put it in the "hard" category?

Title: Re: 13 pirates
Post by yoyoy on Oct 11^th, 2013, 4:04pm

This is what I have understood:

They decide that the safe should be able to be opened if any majority of pirates agree but not be able to be opened if any minority agree.
Implies that 7 out of 13 should have a unique lock to open.

And 13 people can be bifurcated in a group of 6 and 7 by 13C7 ways.
So, lets say for the case of 3 pirates. If pirate no. 1 and 2 agree to open, they should be able to unlock.
So, lets say there were only 2 locks,
cases: Persons who agrees to open lock:-
- 1,2 => 1 has L1 key, 2 has L2 key
- 2,3 if this was the case that there were 2 locks only, then, acc. to this case, L3 should have got L1 key
- 1,3 implies 3 has L2 key
Implying 3 has L1 and L2' keys.
But, then ques says that minority should not be able to open the lock. Also, a pirate can't hold all the keys. Hence, by contradiction, 3 must have some other key that is L3' key.
So, L1 can be opened by 1
L2 by 2
L3 by 3
Implying 1 has L1 keys, 2 has L2 and 3 has L3 keys
But, if say, 1 and 2 agrees to open the box, they should be able to do so.
So, lets say I give key of L3 to 2.
Hence, 2 has keys to L2 + L3
Following all the combinations, 3 should have L1 key too.
So, 3 has L1 + L3 keys
So, 1 must have L1 + L2 keys.

Now how should reach to 5 pirate logic and then eventually 13 ?

Title: Re: 13 pirates
Post by yoyoy on Oct 11^th, 2013, 4:05pm

persons who agree*

Title: Re: 13 pirates
Post by Grimbal on Oct 12^th, 2013, 10:22am

Let's take a group of 6 pirates. There is at least one lock such that none of the pirates has the key. Let's call it lock L.
But if you add one pirate to the group, they are 7 and they can open all the locks, which means the 7th pirate has the key to lock L.
That is the case for any pirate you add, so every pirate other than the 6 does have the key to lock L.
This means that for every set of 6 pirates, there is one lock such that the 6 pirates don't have the key, and the 7 other do have the key.
Obviously, the lock is different for each set of 6 pirates. Therefore, there must be as many locks as there are sets of 6 pirates. There are 13C6 such set, so there are at least 13C6 locks. That's 1716 locks.

PS: as others have concluded before.

Title: Re: 13 pirates
Post by yoyoy on Oct 12^th, 2013, 8:58pm

"Let's take a group of 6 pirates. There is at least one lock such that none of the pirates has the key. Let's call it lock L. " - Bcoz each pirate can't have all the keys with him. r8?

"But if you add one pirate to the group, they are 7 and they can open all the locks, which means the 7th pirate has the key to lock L. " - Why are you saying that they all can open all locks? Pls explain the logic.

Title: Re: 13 pirates
Post by pex on Oct 13^th, 2013, 11:44am

on 10/12/13 at 20:58:36, yoyoy wrote:

"But if you add one pirate to the group, they are 7 and they can open all the locks, which means the 7th pirate has the key to lock L. " - Why are you saying that they all can open all locks? Pls explain the logic.

Quote:

the safe should be able to be opened if any majority of pirates agree

Title: Re: 13 pirates
Post by antkor on Dec 16^th, 2013, 4:42pm

how about a variation of this, having 5 pirates and the captain and at any given time the chest can be opened by any three pirates or the captain and two pirates? anyone wanna try that?

Title: Re: 13 pirates
Post by rmsgrey on Dec 17^th, 2013, 7:46am

on 12/16/13 at 16:42:50, antkor wrote:

how about a variation of this, having 5 pirates and the captain and at any given time the chest can be opened by any three pirates or the captain and two pirates? anyone wanna try that?

That's just 6 pirates, any 3 can open the chest, but you've called one of the pirates "captain"

For that, you need 15 locks, with 4 copies of each key, so that each pair is missing a lock.