Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Oct 29, 2009

King's Poisonous Wine

Jaadu asked me this puzzle during our work visit to IBM Pune

Problem:

You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1024 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.

The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.

You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.

You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.

What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?


Solution:


Highlight the part between the * symbols for the answer.
* 10 prisoners must sample the wine.

Number all bottles using binary digits. Assign each prisoner to one of the binary flags. Prisoners must take a sip from each bottle where their binary flag is set.

With ten people there are 1024 unique combinations so you could test up to 1024 bottles of wine.

Each of the ten prisoners will take a small sip from 512 bottles. Each prisoner will have at least a fifty percent chance of living. There is only one binary combination where all prisoners must sip from the wine and in that case, all the 10 prisoners die. *

No comments:

Post a Comment