Pirate Padlocks (Old combinatorics puzzle)

[jack]

Suppose five pirates have one chest with clasp through which can be threaded many padlocks, many padlocks with keys[1], and a key-cutting machine. They wish to lock the chest such that any three of them may open the chest (but fewer can't). How can they do this? What is the fewest number of padlocks necessary?

[1] Assume each padlock starts with only one key, but the key can be duplicated so several pirates can have a key to the same padlock. Label each padlock 125 if only pirates 1,2 and 5 have a key for it.

Answer 1

Suppose each padlock must be locked round the clasp (ie. so the chest can only be opened when all the padlocks are unlocked). Suppose there are a minimum number of padlocks used.

Lemma 1. Can there be a padlock 1234 in the minimum solution? There must be other padlocks. If any of those padlocks can be opened by a subset of pirates 1, 2, 3 and 4, eg. is padlock 123, then the chest can be opened if all the rest of the padlocks can be opened (open 1234 with the pirate who opened 123), and the chest can't be opened if all the rest of the padlocks can't be opened (duh). So 1234 is useless, but we assumed a minimum number were used.

Therefore, pirate 5 must have a key to the rest of the padlocks (else they can be opened by a subset of pirates 1234). So pirates 1 and 5 can open all the padlocks. So there can never be a padlock 1234 in the solution.

Lemma 2. Can there be a padlock 12 in the minimum solution? Duh, no -- then pirates 345 could not open the chest.

Conclusion Therefore, all padlocks have exactly three keys. Ie. each padlock represents a single pair of pirates who can't open it.

There are ten possible pairs of pirates to be defended against (n12,n13,n14,n15,n23,n24,n25,n34,n35,n45). If those ten padlocks are used, then the chest can't be opened by any pair (that pair can't open their corresponding padlock). But any three can open the chest -- every padlock excludes only two pirates, so does not exclude one of the three, who can open it.

So ten padlocks is a solution. And there is no smaller solution, since if you omit any of those padlocks, that pair can open the chest.

Answer 2

Take five padlocks, one for each pirate, and ten lengths of heavy chain.

Lay the padlocks out on the points of a pentagon. (Or if you prefer satanic pirates, invert the pentagon and use a pentagram.)

Thread a length of chain between each adjacent padlock. (Ie. thread a link onto one padlock, and a link at the other end onto the other.) Thread a length of chain onto padlock #1, over and downwards through the chest's clasp, and onto padlock #3. Then repeat for padlocks #2 and #4, #3 and #4, #4 and #1, and #5 and #2.

I can't explain without a diagram, but if you draw it out, you'll observe that blanking out any three padlocks (without loss of generality 123 or 124) leaves all chain loose, and blanking out any two (without loss of generality 12 or 13) leaves a closed loop of chain and padlocks passing through the clasp.

I'm fairly sure 5 padlocks is minimal, but I can't prove it. Nor can I generalise to a larger number of pirates.

Comments

[simont]

Wow, answer 2 is lovely! Answer 1 was the only one I knew of.

Minimality of five padlocks: with any fewer, there is no antichain of size 5 among the subsets of the padlocks. Hence there must be some pirate A whose set of keys is a superset of that of another pirate B. Therefore, any group of three pirates including both A and B can open the chest iff the same group without B could do so (since B's presence in the group makes no difference to the set of locks that can be unlocked).

eta: Rubbish and nonsense; with four padlocks the subsets of size 2 form an antichain of size 6. Oops. Still, that at least narrows down the form that any four-padlock solution would have to take. Hmm.

[cartesiandaemon.livejournal.com]

Wow, answer 2 is lovely! Answer 1 was the only one I knew of.

Thank you! I definitely had heard the puzzle somewhere, but couldn't remember where, (and later on couldn't find an answer on google either). I started off expecting some crazy physical arrangement of padlocks to be the solution, imagining all combinations would be just too many.

It quickly became apparent that #2 couldn't be the official answer, because it didn't involve duplication of keys, but I obviously wanted to solve it too :) (I think the traditional phrasing excludes solution #2.)

And then I went back and constructed solution #1. Only when I was trying to prove it this morning, did I realise the proof was easy, and indeed helpful in producing the answer.

I technically still don't know if ten padlocks and no chain can be reduced by any arrangement of the padlocks -- I guess it might, but not prettily.

[cartesiandaemon.livejournal.com]

eta: Rubbish and nonsense;

Oh, and it sounded so convincing too... Still, it sounds like a solution is just round the corner.

[simont]

Aha, try this. The point is not that you need an antichain of size <number of pirates>; you need an antichain of size <number of pairs of pirates>. That is, you need an antichain of size 10, which you can do with five padlocks but not with fewer.

If you haven't got such an antichain, then there must be two pairs of pirates such that one pair A,B has a superset of the other pair's keys. Thus, pick a third pirate C from the second pair (there must be at least one who isn't in the first pair), and you have a set of pirates A,B,C with the same keys between them as the pair A,B.

I think I believe it this time.

eta: To clarify, in both this and my previous attempt I am using "superset" in the non-strict sense. If you merely have two pairs of pirates who each have the same set of keys, that suffices.

[cartesiandaemon.livejournal.com]

OK, I think that's convincing. (Do you know if it scales to larger n and p?)

[simont]

Don't see why not. Might get a bit weird if p isn't about n/2, though: I think all I've shown is that the size of the largest antichain (which is always (n choose floor(n/2))) must be at least the number of maximal sets of pirates you want not to be able to open the chest. So as long as (n choose (p-1)) = (n choose floor(n/2)), I think my proof works unchanged; but if you want, say, any three pirates of 48,000 to be able to open the chest then I think my proof won't show that you need at least 48,000 keys: all it'll show is that you need at least 18.

[cartesiandaemon.livejournal.com]

OK, that sounds good. I feel pretty confident in the solution.

[(Anonymous)]

The pirates don't have any chains.

[simont]

A grotty but workable chain-based solution for arbitrarily many pirates, I think. Suppose you have N pirates in total, and you want any p to be able to open the chest.

For each maximal set of pirates you want not to be able to open the chest between them (i.e. every distinct set of p-1), imagine there being a loop of chain through the clasp. Now break that chain at N-(p-1) points, and reattach each break point using a padlock openable only by a pirate not in that set of p-1. Thus, that particular set of p-1 pirates cannot break the closed loop, but with the help of any extra pirate they can.

Unfortunately, we've now got an enormous number of padlocks. But that's OK: every padlock is one which only a single pirate can open, so there are only N distinct types of padlock. So simply merge all the padlocks belonging to each pirate into one big padlock, by rerouting all the affected chain-loops so that the same padlock hasp goes through the ends of all of them. The chains are all flexible one-dimensional things in a three-dimensional space, so it can't be impossible to rearrange them this way.

[simont]

Which, come to think of it, is exactly what your solution is doing; certainly all those loops exist in your solution and they are all topologically linked to the chest clasp. The only difference is that you've cleverly merged a lot of my lengths of chain, so that your solution ends up using only 10 lengths of chain where the above general procedure would have to use (N choose p-1)*(N-p+1) = 30.

In which case, I suppose, the interesting question now becomes how few pieces of chain you can get away with in the general case.

[cartesiandaemon.livejournal.com]

Which, come to think of it, is exactly what your solution is doing

When I invented it, I guessed it would be a special case of something like this, but couldn't show it.

In which case, I suppose, the interesting question now becomes how few pieces of chain you can get away with in the general case.

Yeah, it didn't feel right proposing a solution with an obviously non-minimal number of chains, even though that's technically ok. I agree finding the minimum number of chains is likely to be the interesting/hard bit (I gracefully bowed out, I'd need to draw a lot of examples to work out where to start).

[cartesiandaemon.livejournal.com]

Yeah, I think that works. I started with something very similar, but didn't get it to a point where I was sure before I intuited the pentagon version. I think it works, but would need a lot of diagrams to be sure it actually does...

[ptc24.livejournal.com]

Hmmm, I was puzzled by your description at first: why have a clasp that you can thread a key-cutting machine through?

[alextfish.livejournal.com]

Yes, I thought that too :)

[cartesiandaemon.livejournal.com]

:)

[rochvelleth.livejournal.com]

It's it's... it's like one of those puzzle books I used to do when I was young!

And indeed I think you've just come up with the plot for POTC4, so you'd better send it off to Disney before they come up with another ;)

[cartesiandaemon.livejournal.com]

:) I don't know, the plot coped with giant squid, but I'm not sure it'll cope with logic :)