wu :: forums
« wu :: forums - 13 pirates »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 3:04pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: towr, SMQ, Grimbal, william wu, ThudnBlunder, Icarus, Eigenray)
   13 pirates
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: 13 pirates  (Read 15867 times)
klbarrus
Newbie
*





   


Posts: 29
13 pirates  
« on: Jul 25th, 2002, 9:59pm »
Quote Quote Modify Modify

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.
IP Logged
Frothingslosh
Guest

Email

Re: 13 pirates  
« Reply #1 on: Jul 25th, 2002, 10:31pm »
Quote Quote Modify Modify Remove Remove

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.
IP Logged
klbarrus
Newbie
*





   


Posts: 29
Re: 13 pirates  
« Reply #2 on: Jul 25th, 2002, 10:55pm »
Quote Quote Modify Modify

Admirable, but I think you are stretching it with your assumption Wink
 
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.
IP Logged
Frothingslosh
Guest

Email

Re: 13 pirates  
« Reply #3 on: Jul 25th, 2002, 11:29pm »
Quote Quote Modify Modify Remove Remove

  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.
 
IP Logged
klbarrus
Newbie
*





   


Posts: 29
Re: 13 pirates  
« Reply #4 on: Jul 26th, 2002, 12:29am »
Quote Quote Modify Modify

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! Wink
IP Logged
S. Owen
Full Member
***





   


Gender: male
Posts: 221
Re: 13 pirates  
« Reply #5 on: Jul 26th, 2002, 11:43am »
Quote Quote Modify Modify

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.
IP Logged
Alex Harris
Guest

Email

Re: 13 pirates  
« Reply #6 on: Jul 26th, 2002, 11:37pm »
Quote Quote Modify Modify Remove Remove

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.
IP Logged
cnmne
Guest

Email

Re: 13 pirates  
« Reply #7 on: Jul 28th, 2002, 5:36pm »
Quote Quote Modify Modify Remove Remove

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 Smiley
IP Logged
tim
Junior Member
**





   


Posts: 81
Re: 13 pirates  
« Reply #8 on: Jul 30th, 2002, 7:53pm »
Quote Quote Modify Modify

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





   


Posts: 33
Re: 13 pirates  
« Reply #9 on: Oct 11th, 2013, 4:04pm »
Quote Quote Modify Modify

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 ?
IP Logged
titan
Newbie
*





   


Posts: 33
Re: 13 pirates  
« Reply #10 on: Oct 11th, 2013, 4:05pm »
Quote Quote Modify Modify

persons who agree*
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: 13 pirates  
« Reply #11 on: Oct 12th, 2013, 10:22am »
Quote Quote Modify Modify

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.
IP Logged
titan
Newbie
*





   


Posts: 33
Re: 13 pirates  
« Reply #12 on: Oct 12th, 2013, 8:58pm »
Quote Quote Modify Modify

"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.
IP Logged
pex
Uberpuzzler
*****





   


Gender: male
Posts: 880
Re: 13 pirates  
« Reply #13 on: Oct 13th, 2013, 11:44am »
Quote Quote Modify Modify

on Oct 12th, 2013, 8:58pm, 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
IP Logged
antkor
Newbie
*





   


Posts: 30
Re: 13 pirates  
« Reply #14 on: Dec 16th, 2013, 4:42pm »
Quote Quote Modify Modify

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?
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: 13 pirates  
« Reply #15 on: Dec 17th, 2013, 7:46am »
Quote Quote Modify Modify

on Dec 16th, 2013, 4:42pm, 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.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board