Fog Creek Software
Discussion Board




screwy pirates solution incorrect

The solution says that it works for any amount of pirates but it doesn't.

If you say there are only 2 pirates and you need one to agree to open the chest then the solution given says you need 2 locks and one key.

It is obvious that you only need 1 lock and one key for that situation.

Tom
Monday, January 03, 2005

I agree with Tom.  The same is true if you have 4 pirates and need 3 to agree.  The solution states that you need 4 locks and each pirate gets three locks.

The works out like so....
      L1  L2  L3  L4 
P1  Y    Y    Y   
P2  Y    Y    Y 
P3        Y    Y  Y   
P4        Y    Y  Y

But if they all have Locks 2 and 3, then why do you even need those locks.

      L1  L4
P1  Y 
P2  Y 
P3        Y
P4        Y


Try figuring out 5 pirates where 3 need to agree. 

These problems are not trivial, and the distribution of the keys requires a genius locksmith if 13 pirates each get 924 locks!

BTW: Assuming you always need a majority (>50%)...

2 pirates:
Both pirates must agree.  2 locks, one key each.

3 pirates:
2 must agree. 3 locks, 2 keys each

4 pirates: above

The logic of the proposed solution makes sense for larger numbers.  But, can it be proven that the problem cannot be solved with fewer locks?

Cheers,
Will

Will Smith
Monday, January 10, 2005

Will: P1 and P3 can work together to open the lock. I believe the solution given is correct and optimal; here's another crack at it.

Suppose there are n pirates and they want any m but no m-1 to be able to open the chest. (Obviously n >= m > 0.) They should order the locksmith to make a lock for every distinct group of n - (m-1) pirates and give keys that open it to each member of that group. No group of m-1 can open the chest because the other n - (m-1) will have a key they don't have. Any group of m, however, has all the keys, since given a key, at most m-1 of the members can fail to have it.

This yields Tom's solution when n=2 and m=1, since there is exactly one distinct group of n - (m-1) = 2 pirates, namely, the entire group.

To see that this scheme is always optimal, consider any valid system of locks and keys. Fix a group of m-1 people. Since it takes m people to open the chest, there must be some lock L to which they have no key. With help from any other person, however, the group must be able to open L. Thus everyone outside the group has a key to L, from which it follows that every group of n - (m-1) people must have its own lock.

David
Monday, January 10, 2005

how about this:


        1  2  3  4  5  6  7  8  9  10  11  12  13
#1    x  x  x  x    x  x  x
#2        x  x  x    x  x  x  x
#3              x  x    x  x  x  x  x
#4                  x    x  x  x  x  x    x
#5                        x  x  x  x  x    x    x
#6                              x  x  x  x    x    x    x
#7                                  x  x  x    x    x    x    x


seven locks, seven keys per pirate. no combination of less than 7 opens the lock while any combination of 7 or more does.

ash
Tuesday, January 11, 2005

David,

Also P2 and P4.. .I messed that one up...  But nevertheless, based on the solution, how do you put together 4 locks with each pirate holding three keys?

ash,

What if #1 and #7 got together?

Will Smith
Friday, January 14, 2005

*  Recent Topics

*  Fog Creek Home