## Monday, July 2, 2007

### Poisoned Wine Puzzle

Find the minimum number of prisoners required to find the poisoned bottle from the 1000 bottles with in 24 hours!!

You are the owner of a renowned Wine catering services. You have a biggie offer of catering service to a party for the Queen of your place. So they have ordered a thousand bottles of wine (Yes a 1000!!!).
You are obviously so happy about it and worked hard to arrange the complete order. But suddenly tragedy occurred, one of you employee accidentally mixed a poisoned bottle with the wine bottles in the container. Being the same type of bottle you are not able to distinguish it without drinking and the death occurs in 24 hours after drinking.
The ceremony being tomorrow , the queen will order for your execution, if the order is not completed. Now you have to find a solution to it. You cannot have another 1000 bottles and you have to figure out that bottle. The queen takes care of this situation and tells you that you have 1000 prisoners to let them drink the bottles and find out the poisoned bottle.

Find the minimum number of prisoners required to find the poisoned bottle from the 1000 bottles with in 24 hours!!

1. Hey good problem. I loved solving it.

I think 10 should be enough.

Procedure to find out poisoned bottle:-

1. Number all the bottles in binary fashion. Start numbering from 0. i.e. 0000000000 (0) to 1111101000 (1000).
2. Let each prisoner stand for one digit.
3. Lets say the one in Unit's place is no1 and two's places is no2 4s place is no3 and so on.
4. Each prisoner will drink a sample from a bottle if the number at his position is one. e.d for the 255th bottle, binary is 0011111111, so no 1 to no 8 will drink this.
for no 8 bottle, 0000001000 so only no 4 will drink.

5. At the end of 24 hours just see who has died, and fill one at his place and fill zero on the place who hasn't died. Say no 2, no5 and no 7 die. so we have

0001 0100 10 thus 82nd bottle has poison.

Hope I am correct. Cause i've spent a lot of time over this.

2. nc0 + nc1 + .. ncn = 1000 then the value of n is the answer. ( dont remember the theorem so could nt calculate the ans)

soln:
say the n: 10 (suppose)

1. then i would ask each of the 10 prisoners to take one bottle each (so 1000 -10 = x)
2. Now i would make teams of 2 prsoners each and make each of the team to have from one bottle ( so 10C2 or nc2)
3. again this tiem team of 3 and each team drinks from single bottle (10c3 or nc3)
4. and so on...
5. supposing that one person died! means check the single bottle drinker
6. supposing that 2 pple died means a team of 2 pple died check what team and what btle
7. etc

what do u say???

3. nc0 + nc1 + .. ncn = 1000 then the value of n is the answer. ( dont remember the theorem so could nt calculate the ans)

soln:
say the n: 10 (suppose)

1. then i would ask each of the 10 prisoners to take one bottle each (so 1000 -10 = x)
2. Now i would make teams of 2 prsoners each and make each of the team to have from one bottle ( so 10C2 or nc2)
3. again this tiem team of 3 and each team drinks from single bottle (10c3 or nc3)
4. and so on...
5. supposing that one person died! means check the single bottle drinker
6. supposing that 2 pple died means a team of 2 pple died check what team and what btle
7. etc

what do u say???

4. 10 prisoners are enough , as u have already proved.
and this is the minimum number of prisoners as if there were x number of prisoners req , x < 10
then , there are 2**x possible outcomes . like first person dying , second surviving ...
these are 2**x possible cases ,and wed like to determine from these 2**x cases the number of the bottle that was poisoned.
if 2**x < 1000 , then we cant assign a mapping from these 2**x cases to the number of bottles
that covers all the 1000 bottles.
Thus 2**x >= 1000
hence x >= 10

Hence 10 is the minimum :)

5. well there is actually a way you only need 9 people.
so you split up the 1000 into 500 and let one prisoner taste them. So he either dies or not. If not you take the next 500 if he dies you take the 500 tested. you do the same thing again split it into 250.... and you get down to 2 with 9 people so thats the answer 9 is the minimum
here are the steps
1000/2
1)500
2)250
3)125
4)63
5)32
6)16
7)8
8)4
9)2
if prisoner 9 dies you know its the bottle he drank out of, if he does not die its the other. Also it would be a maximum of 9 prisoners needed(potentially dying) maybe you need less prisoners because the bottles were not poisoned.

6. anonymous - your method would not work due to the fact that the poison takes 24 hours to kill you (presumably more like 23 so you can put the wine out in time!) and you only have 24 hours to find which one. If you had no time limit this would still kill too many because with limitless time I would manage this with only 1 prisoner by making him drink from the next bottle every 6 hours and then when he dies, just work back 24 hours to which bottle he drank from! Anyway, the riddle says 24 hours limit so 10 is the minimum using binary as stated by swan.

7. We could further divide the bottles into 500 - 500
and this 500 will be further divided into 250-250 and then 250 will further be divided into 100 - 100 -50
and the 100's will be divide into 50-50-50-50-50 along with the earlier 50
Ask 25 to sample bottles from 1-25 each in each one of the groups
The best case is that someone from one of the groups dies and u have found the bottle because they are all numbered. Loss is 125 bottles

The worst case is that we find the bottle in the last iteration then the minimum number of bottles will be 500.

8. The minimum number is 1 dudes.