Hard puzzle round, usually with heavy hinting.
One hundred prisoners and one hundred boxes
The question
One hundred prisoners must each find their own number among one hundred boxes, opening at most fifty each, with no communication. All must succeed. What strategy beats 2^-100?
Have a go before you open the solution. If you are stuck after a few minutes, the first paragraph below is usually enough of a nudge.
Show the worked solution
The answer
Follow the permutation cycle from your own box number. Success probability about 31 percent.
Each prisoner opens the box with their own number, then the box whose number they just found, and continues.
The boxes define a random permutation, and this strategy succeeds for a prisoner exactly when their cycle has length at most fifty.
All prisoners succeed together precisely when the permutation contains no cycle longer than fifty, which happens with probability 1 minus the sum of 1/k for k from 51 to 100.
That is about 1 - ln 2, roughly 31 percent. The lesson is that correlating the outcomes, rather than improving any individual's chance, is what makes the problem tractable.
What it is testing
Whether you look for dependence between outcomes instead of optimising one in isolation.
Try these next
Two ropes, forty five minutes
Warm-upTwo ropes each burn for exactly one hour but not at a uniform rate. Using only these, measure forty five minutes.
One thousand bottles, one poisoned
StandardOne of one thousand bottles is poisoned, and the poison acts in exactly one day. How many testers do you need to identify the bottle in a single day?
The blue-eyed islanders
HardOn an island everyone sees others' eye colour but not their own, and anyone who deduces theirs is blue must leave that night. A visitor says aloud 'at least one of you has blue eyes'. With one hundred blue-eyed islanders, what happens?
Estimate the piano tuners
StandardHow many piano tuners work in New York City?
Preparing properly
Live opportunities
Interviewing soon? See who is hiring
Open vacancies we track at quant firms, grouped by role and city. Adverts are anonymised.
Hiring for these roles? Brief the desk on a hire or check your fit for a role.
Research desk
Speak to a quant market specialist
Ask what a firm really pays, how a desk hires, or where your profile sits. One reply from the research desk, in confidence, no obligation.