Puzzle : King’s poisonous wine cellar

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

Advertisements

Tags: ,

6 Responses to “Puzzle : King’s poisonous wine cellar”

  1. Puzzle : A better solution to king’s wine cellar « Me, Myself and Mathematics Says:

    […] 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. […]

  2. Rama.B Says:

    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..

  3. ashish Says:

    ya its for sure 7.As above stated

  4. NikhiL RuikaR Says:

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

  5. pradeep Says:

    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

  6. Sum Body Says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: