Skip to content

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 66 or more pirates can open every lock, while any group of 55 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

462462 locks, with 252252 keys per pirate. Every group of 55 must be locked out of some lock whose keys all the other 66 pirates hold, and two different groups of 55 cannot share that lock (their union has at least 66 pirates), so you need (115)=462\binom{11}{5}=462 locks. Each pirate holds a key to every lock belonging to a 55-group without them: (105)=252\binom{10}{5}=252.

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 solution

Lessons behind this question

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