1000 bottles, one poisoned, ten mice, one day.
The poisoned wine puzzle: one of 1000 bottles is poisoned, the poison takes a full day to act, and you have ten mice and one day. Find the bottle. The answer is a binary encoding, and the follow-up with two days is where the real thinking starts.
A king has 1000 bottles of wine and learns that exactly one is poisoned. The poison is undetectable by taste or smell, any quantity of it is fatal, and it acts after exactly 24 hours: a mouse that drinks from the poisoned bottle dies at the 24-hour mark, not before, and a mouse that drinks from any number of clean bottles is unaffected. The feast is in 24 hours. The king has ten mice.
Identify the poisoned bottle in time for the feast, using at most ten mice.
A mouse per bottle would need a thousand mice. Dividing the bottles into ten groups of a hundred and giving each mouse one group tells you only the group. The gap between "ten mice" and "a thousand bottles" is the puzzle, and the way across it is to stop thinking of a mouse as testing a group of bottles and start thinking of the set of mice that die as a message. How many distinct messages can ten mice send?
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
After 24 hours, each mouse is either dead or alive: a pattern of ten yes-or-no outcomes. That is 2 to the power 10, which is 1024 distinct patterns, more than 1000.
Hint 2 the key move
Number the bottles 0 to 999 and write each number in ten-bit binary. Let mouse i drink from every bottle whose i-th bit is 1. A mouse can drink from many bottles safely; only the poisoned one matters.
The solution
Reveal the full solution
Number the bottles 0 to 999 and write each number as a ten-bit binary string. Mouse number i, for i from 0 to 9, drinks a sip from every bottle whose bit i is 1. Each mouse drinks from about 500 bottles, which is fine: clean wine does nothing.
After 24 hours, read the mice as bits: dead means 1, alive means 0. The resulting ten-bit number is the poisoned bottle. It works because the only bottle that kills anything is the poisoned one, so the set of dead mice is exactly the set of positions where that bottle's number has a 1. Every bottle has a distinct number, so every possible outcome names one bottle. Bottle 0, whose bits are all zero, is identified by no mice dying at all.
The capacity argument shows ten is the minimum. With m mice and one round, there are 2 to the power m possible outcomes, and to distinguish 1000 bottles you need at least 1000 of them. Since 2 to the power 9 is 512 and 2 to the power 10 is 1024, nine mice cannot suffice and ten can. Every mouse is a bit of a 10-bit counter, and the poison writes the counter for you.
What this puzzle is really testing
Whether you see a test as one bit of an encoding rather than as a probe of one group. The same shift powers group testing in real laboratories, where samples are pooled so that a few assays locate the positive one among many. It is also the direct ancestor of the gold bar puzzle, where binary place values cover a range with few pieces, and the outcome-counting bound is the argument from the eight balls puzzle with 2 in place of 3. The binary search on the answer deep-dive shows the same halving structure at work inside an algorithm.
Follow-ups to expect
The good one: you have 48 hours instead of 24, and may run a second round with the surviving mice. Now each mouse has three outcomes (dies on day one, dies on day two, survives), so m mice yield 3 to the power m patterns; since 3 to the power 6 is 729 and 3 to the power 7 is 2187, seven mice suffice. The encoding is base three, with a mouse drinking on day one, day two, or never, according to the digit. Then the awkward version: two bottles are poisoned. Dead-mouse patterns are now the bitwise OR of two numbers, which is not unique, and the clean binary scheme breaks; that is where the interviewer wants to see you reason rather than recall.