Tan Kin Lian's Blog: Identify the poisoned wine

Friday, February 15, 2008

Identify the poisoned wine

CAN YOU SOLVE THIS PUZZLE?

A king has 1000 bottles of wine. An assasin tried to poison the wine. The king's guards caught the assasin after he poisoned only one bottle, but they did not know which bottle was poisoned.

It is known however that the poison is so powerful that even a tiny bit of the poisoned wine will kill, and it is known also that the poison will only kill after 24 hours. The king order you, his advisor, to get some of the criminals in the dungeon to test the wines for him. The king expects to find out the result the next day, essentially 24 hours after the testers drink the wine.

Now the simplest way is if 1000 criminals were available, just get them to each drink a little bit from each of the 1000 bottles. Hence, the poisoned bottle will be identified when one particular tester, out of the thousand testers, dies the following day. However, only 10 criminals is imprisoned in the dungeon on that particular day!

Is there a way to identify the poisoned bottle by the following day using only 10 testers? What is the method?"

12 comments:

KE said...: yup, in fact it would be possible even with 1024 bottles of wine...; February 15, 2008 10:31 PM
Victor Foo said...: The bottle which was opened is obviously the bottle that was poisoned, right ? :)

Okay. This is a binary question, gentlemen.; February 15, 2008 11:44 PM
eng60340 said...: intersection of 3 x-y-z planes; February 16, 2008 12:05 AM
eng60340 said...: damn. my xyz plane solution requires 30 prisoners.

sorry sorry. :)

suspect that it's probably something 2^10 stuff. but it's beyond me. boohoo. boohoo.; February 16, 2008 12:16 AM
eng60340 said...: final attempt. should be correct already.

label the wine in binary.

arrange the prisoners to be the place holder for binary and drink if it's 1 in that place holder.

e.g.

wine number 109 is 1101101 in binary

so if only prisoner A,B,D,E,G dies then 109 is poisonous.

..not very elegant way of explaining....but it works!; February 16, 2008 12:41 AM
Tan Kin Lian said...: eng's reply at 12.41 is correct. the explanation is quite clear.; February 16, 2008 9:18 AM
Anonymous said...: What about dividing the 1000 bottles to 10 lots of 100 bottles each, then ask each tester to taste 100 bottles each. This will shortlist the suspect poison to 100 bottles, with 9 testers left.

Then divide the 100 bottles to 9 lots with 8 lots of 11 bottles each and the 9th lot of 12. Repeat the testing and this will shortlist the poison to at most 12 bottles, leaving 8 testers.

Continue the process and as a bonus, there should be at least 5 testers still alive.

Can or not, Mr Tan?; February 16, 2008 12:26 PM
Tan Kin Lian said...: The correct answer is the one described by eng.; February 16, 2008 1:16 PM
Anonymous said...: From a layman perspective, we can think of each person representing 2 atates, either dead or alive. Thus 10 people can represent 10^2 = 1,024 states. Using the binary system proposed by eng, each person can represent a placement from the least significant bit the most significant bit. So once we find out the poisoned wine, we lay all the bodies out and use it to decode each bottle is poisoned. e.g. 1010101010 means bottle 682.

Next puzzle. Three colleagues came together and managed to find out their average salary without knowing each other's salary. How did they know how to do it?

HK; February 16, 2008 6:17 PM
Anonymous said...: Ask each other. Ha ha ha!; February 18, 2008 1:11 PM
dsowerg said...: I was thinking something more along the line of the amazing numbers! But that would take some reverse engineering. The binary solution is cleaner.; February 20, 2008 9:45 AM
enricoGi said...: I had this question today in an interview in Dublin for a job as software engineer. In my case there was only 8 bottles of wine. Now that I know the solution it seems so obvious but today it wasn't so easy...; February 26, 2008 4:42 AM