Sunday, February 13, 2011

Finding the Poison Bottle

A king has arranged a celebration with many visitors to his kingdom. In the celebration, they arranged drinks in 1000 bottles. Just one hour before the celebration, he came to know that, one person has included a poison drink of the same color in a bottle of the same shape. If anyone drinks poison, then nothing happens to that person for one hour. After one hour, suddenly that person would die.

The king has few criminals who are going to be hanged the next day. With the help of them, he can find which bottle has poison. How many minimum no.of criminals he needs to find out the poisoned bottle in one hour.

Answer:
He needs 10 criminals.

Every bottle is given a no from 0 to 1000. Convert each number to binary. The binary number would contain 10 bits. For the first criminal, give little drink from all the bottles for which the first bit is 1. Similarly, for the second criminal, give drink from all the bottle for which the second bit is 1. Do the same thing for all the ten criminals.

After one hour, form a binary number with the criminals. If the first criminal dies, then make the first bit 1. If the second criminal does not die, then make the second bit 0. Do the same for all the criminals. Convert the binary number to the corresponding decimal number. That bottle has the poison.