King Bear & Poison ..Very Common & Tough Puzzle

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.


Soln By –Saurabh Joshi from his blog me.maths & puzzle
i found its interesting so i pasted here