Well,

It has been a couple of days since I have posted anything here. Posting a very simple puzzle over here.

**Problem :** A king has a wine cellar with 100 drums of wine. A traitor sneaked into his wine cellar to poison the drums. He could mix poison in only one of the drums when guards caught him. However, guards could not see which one drum was poisoned. Our king being a drunkard wishes to be able to drink wine as soon as possible but safely. The poison guarantees that the person drinking the wine would die in 10 days.

Being a king, he can order his servants to drink wine from the drums to find out poisonous drum. However, he wishes does not want to risk lives of too many servants.

1) King wishes to be able to drink some wine on 11th day. How many servant would be needed to take the risk of drinking wine before figuring out a harmless wine drum?

2) King wishes to throw a grand party on 11th day. How many servant would be needed for figuring out the poisonous wine drum?

**Solution : **

The solution to the first problem is extremely simple and obvious. Only one servant need to drink any one of the wine drum. If the servant dies, all the other drums are harmless. If he does not die, we can guarantee that at least that one wine-drum is harmless.

Well, second problem has actually two sides to it. Say for example, king wishes that number of servant to be put on stake can be arbitrarily large, but the number of servant died during the process should be less. Then, we need 99 servant for each wine drum. At most one servant would die in this case.

However, what if we want to minimize the number of servants to be put on stake? Initially I went on a very wrong direction. That was to use prime factorization of every number from 1 to 100. For example, there will be a servant drinking from wine-drums which are numbered in multiple of 2, and similarly another servant for multiple of 5. So, we would be able to detect number 10 as the poisonous drum if both of them dies. Using this multiple scheme, number of servant needed would be

2,4,8,16,32,64

3,9,27,81

5,25

7,49

all primes number between 1 to 100 which has not appeared in the above list.

Basically, the number comes out to be huge. Certainly a very very bad solution.

A good solution would be to arrange wine-drums in 10×10 maze. We would need only 20 servant. 10 servant for the row and 10 for the column. So when in 10 days i-th servant for row and j-th servant for column dies, we would know that the drum located at (i,j) is the culprit. But still we are far from the best solution.

We can visualize the maze in three dimension. 5x5x5 would need only 15 servants. Of course, there would be some spots empty in the maze, but that does not matter.6x6x3 = 15. Going ahead we can have 5x5x4=14.

It seems we can still push it further. We can visualize the maze in four dimension. 4x3x3x3 = 13. This is the least possible number I could find. I don’t know whether we can push it still further down. If you can figure out a still smaller number, please comment on this post.

–Saurabh Joshi

June 10, 2008 at 9:52 am |

[…] Sometimes it happens that you are so much biased to think in one direction that you forget to think that a simpler and better solution might exist from a different direction. I am referring to my post on the king’s wine cellar. […]

August 29, 2008 at 4:54 pm |

I think its 7. Express each number in binary, and arrange 7 servants in a row, whenever u get a 1 in the number, give that to corresponding position servant.. atlast, find out which all servants died.

ex: if 53rd bottle contains poision,

then the following will be a scenario.

0011 0101.

So starting from left, servants at posiitions, 3,4,6,8 will die..

November 3, 2010 at 12:29 pm |

ya its for sure 7.As above stated

August 12, 2011 at 6:15 pm |

thank u very much saurabh……d same Q was asked to me in 3dPLM aoti today

November 1, 2012 at 12:04 am |

I was asked to solve this puzzle in an interview at Intel . I did it partially well but only with a hint from the interviewer . Now after about an year I thought if I could find it online and found this one .

Thanks

Saurabh

May 4, 2014 at 11:37 am |

For 1024 wines, 2 poisons, 40 tests, look at http://math.stackexchange.com/a/779364/138894