So there's this king. Someone breaks into his wine cellar where he stores 1000 bottles of wine. This person proceeds to poison one of the 1000 bottles, but gets away too quickly for the king's guard to see which one he poisoned or to catch him.
The king needs the remaining 999 safe bottles for his party in 4 weeks. The king has 10 servants who he considers disposable. The poison takes about 3 weeks to take effect, and any amount of it will kill whoever drinks it. How can he figure out which bottle was poisoned in time for the party?
There are a few keys to this puzzle: 1) The king has to mix wine in order to isolate the single poisoned one. 2) There are 10 servants. After about 3 weeks, each one can be either dead or alive, meaning that there are 2^10 = 1024 possible outcomes. Since 1024 > 1000, it's actually possible for some scheme to work. 3) This puzzle is much easier if you have any knowledge of binary numbers
Here's the scheme: The king assigns each servant a number from 1-10. The king assigns each bottle a number from 0-999. When he labels them, though, he writes the number on the bottle in binary with ten digits, like this: 0: 000000000 1: 000000001 2: 000000010 3: 000000011 4: 000000100 5: 000000101 ... 999: 1111100111 and so on. Read this if you don't know binary: http://en.wikipedia.org/wiki/Binary_number.
Now, each servant takes a small sip from every bottle where the servant's number equals 1 in the binary number on the bottle. So, the 1st servant drinks from every other bottle. The second servant drinks from bottles 2, 3, 6, 7, 10, 11, etc.
Then based on the combination of servants that die, he can identify the poisoned bottle. For example, if none of them die, the 0th bottle was poisoned because none of them drank from it. If only servant 1 dies, then bottle 1 was poisoned, because he's the only person who drank from it. Finally, if servants 1, 2, 3, 6, 7, 8, 9, and 10 die, then the 999th bottle was poisoned (see how this matches up with 999 above).
Comments
I was asked this question in a job interview last year. It's a great question that really challenges one's ability to dissect a problem and carefully use the given information. (I'm being intentionally vague so I don't ruin it for others)
Great puzzle! Ignore the jerks.
Guys, puzzles are about the logic of problem, the story is just a delivery. If you are pathetic enough to dissect the entire story then it's probably because you are insecure at being too stupid to be able to reason out a solution.
+1 Michael. This same problem without a supporting story would just be ridiculous.
Reminds me of a very geeky joke:
A geek teaching at school: "Suppose we have 1000 apples. Or let's take a round number... Suppose we have 1024 apples."
Wine tends to only last about a week at most after opening, so the solution seems flawed as the king now has 999 bottles of spoiled wine and a bunch of dead servants.
Furthermore if nobody saw the thief poison a bottle it would be improbable to know that if a bottle was poisoned at all.
That's not to mention the method of injection, which for the sake of argument we will assume hypodermic needles have already been invented. With the amount of pressure it takes to insert a cork into a wine bottle I think it's safe to assume that the needle would have to be big enough to be durable so that it could even puncture the cork.
I would look for floating bits of cork inside the bottle, or assuming the wine had been collected over a period of time, examine the dust around the wine rack.
This comment reminds me of this Richard Feynman interview
That's hilarious!
And why is the solution you were clearly driving me towards one which takes advantage of an undocumented and unreliable epiphenomenon? Does your team usually write code whose correctness relies upon undocumented and unreliable correlations, correlations whose magnitudes can vary widely as a result of implementation details?
I would first try to find out if the poison isn't colorless, and if that's the case, you could inspect the color of each wine. It would be especially obvious if it's white wine.
Awesome riddle!
Some remakes regarding the solution: Key (1) isn't a part of the suggested scheme, and also "every bottle" on line 10 isn't true.
You're right. Perhaps the original intention was to say "each of the servants can/must try multiple wines"?