Locks and keys so any six of eleven can open
Question
Eleven pirates want to secure their treasure chest with several padlocks, distributing keys so that any group of or more pirates can open every lock, while any group of or fewer always finds at least one lock it cannot open. What is the smallest number of locks needed, and how many keys must each pirate carry?
Short answer
locks, with keys per pirate. Every group of must be locked out of some lock whose keys all the other pirates hold, and two different groups of cannot share that lock (their union has at least pirates), so you need locks. Each pirate holds a key to every lock belonging to a -group without them: .
Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 4.2 Combinatorial Analysis, 'Screwy pirates 2', p.66; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solutionLessons behind this question
- Counting and Combinatorics
- Sample Spaces, Events, and the Probability Axioms
- Conditional Probability, Total Probability, and Bayes' Rule
Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.
Read it free