![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackSuppose 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.
[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.