Wednesday, August 04, 2004

Puzzle: King's party!

Poisoned wine
~~~~~~~~~~~~~
A wise king is throwing a party in 30 days. He has 1000 bottles of wine. One bottle is poisoned. The poison isn't detectable and kills after 29 days. To find out which bottle is poisoned he orders a minimal group of people to test the wine.

How many men does it take to find the poisoned bottle?

Select the area below to highlight the answer.

Answer:
-----------

Here is the answer that I could come up with. Don't blame me for its bias to a software guy's talk, but three years doing C coding has blunted my mind.

My answer is 10.

Basically with 10 entities that can take two states (dead or alive) the number of combinations possible is 1024. Now number the bottles from 1 to 1000. For ease of explanation I'm going to ask you to track things in binary. 1000 can be accommodated in 10 bits. So take 10 men and assign one of them to each bit position. Now take each bottle, convert its number to binary and give the wine to all men for whose corresponding position the bit is set in the wine bottles number. After 29 days, see who all are dead. Construct a 10 bit number in which only the bits corresponding to the dead guys are set. The resulting number is the number of bottle that is poisoned.




0 Comments:

Post a Comment

<< Home