Standard puzzle round.
One thousand bottles, one poisoned
The question
One 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?
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
Ten.
Number the bottles 0 to 999 in binary, requiring ten bits.
Assign one tester to each bit position; that tester drinks from every bottle whose number has a one in that position.
After a day, the pattern of which testers are affected reads directly as the binary number of the bottle.
Ten testers cover 1024 bottles, which is the tight bound since each tester yields a single bit of information.
What it is testing
Recognising an information-theoretic bound and building a code that reaches it.
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 hundred prisoners and one hundred boxes
HardOne 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?
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.