**Question:**

A king is about to give a party in 24 hours. For the party they have arranged drinks which will be served through 1000 barrels. Out of jealousy , some one near to king has poisoned one of the barrels. The poison is so strong that even a drop can kill a person. But results are not immediate. A person may die from 13 to 20 hrs. Now king has a duty of finding that barrel. He has 24 hours with him. And he has unlimited prisoners on which the drinks can be tested. Find out the maximum prisoners he would need to find out that barrel.

**Solution:**

1) let's say you are identifying 4 barrels - you need two prisoners - you can mix the wine (or whatever it is) in such a way that either first prisoner dies, second prisoner dies, both die or none die, identifying the right barrel.

Let's say there are eight barrels. Let's number them 1 through 8. You need just three prisoners. First prisoner gets a mixture of 1, 2, 3, 4, second 3, 4, 5, 6 and third gets 1, 3, 5, 7. There are exactly eight combinations of the three prisoners dying or staying alive and with the above mixture each combination of the prisoner's deaths shows exactly which barrel was poisoned.

With 16 barrels you would need 4 prisoners.

The point is that with N prisoners you can 'encode' 2 to the N-th power barrels. With 1000 barrels you would need 10 prisoners.

2) 10 is the correct answer. consider the following

nC0 + nC1 +... +nCn= 2 power nSo upto 1024 barrels can be covered using upto 10 prisoners.

Think it like this. 1 drop from each barrel to ten prisoners. Then 11th barrel will be for both 1st and 2nd prisoner. 12th for 3rd and 4th prisoner. If they both die then this 11th barrel was poisened one. Keep making such combinations for all the barrels and considering all these 10 prisoners.

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

## Click Here To add Comment

Your feedback is always appreciated.

I will try to reply to your queries as soon as time allows.

Please do not spam Spam comments will be deleted immediately upon our review.

Blogger Widgets