Author 
Topic: 13 pirates (Read 12084 times) 

klbarrus
Newbie
Posts: 29


13 pirates
« on: Jul 25^{th}, 2002, 9:59pm » 
Quote 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

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 25^{th}, 2002, 10:55pm » 
Quote Modify

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.


IP Logged 



Frothingslosh
Guest

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 26^{th}, 2002, 12:29am » 
Quote 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!


IP Logged 



S. Owen
Full Member
Gender:
Posts: 221


Re: 13 pirates
« Reply #5 on: Jul 26^{th}, 2002, 11:43am » 
Quote 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 (n1)/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

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

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


IP Logged 



tim
Junior Member
Posts: 81


Re: 13 pirates
« Reply #8 on: Jul 30^{th}, 2002, 7:53pm » 
Quote 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 11^{th}, 2013, 4:04pm » 
Quote 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 11^{th}, 2013, 4:05pm » 
Quote Modify

persons who agree*


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7361


Re: 13 pirates
« Reply #11 on: Oct 12^{th}, 2013, 10:22am » 
Quote 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 12^{th}, 2013, 8:58pm » 
Quote 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:
Posts: 880


Re: 13 pirates
« Reply #13 on: Oct 13^{th}, 2013, 11:44am » 
Quote Modify

on Oct 12^{th}, 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 16^{th}, 2013, 4:42pm » 
Quote 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
Gender:
Posts: 2812


Re: 13 pirates
« Reply #15 on: Dec 17^{th}, 2013, 7:46am » 
Quote Modify

on Dec 16^{th}, 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 



