Problem:

A king has a cellar of 1000 bottles of delightful and very expensive wine. A neighboring king plots to kill the king and sends a servant to poison the wine. Fortunately king’s guards catch the servant after he has only poisoned one bottle. Alas, the guards don’t know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it takes one month to have an effect. The king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever king he knows he needs to murder no more than 10 prisoners to find the poisoned one, and hence will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what is in mind of the king and how will he be able to do so?

Solution:

Think in terms of binary numbers.

Number the bottles 1 to 1000 and write the number in binary format.

bottle 1 = 0000000001 (10 digit binary)

bottle 2 = 0000000010

bottle 3 = 0000000011

.

.

.

.

bottle 500 = 0111110100

.

.

.

.

bottle 1000 = 1111101000

· Now take 10 prisoners and number them 1 to 10

· let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit.

· Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc.

Suppose bottle 925 is poisoned, then

prisoner = 10 9 8 7 6 5 4 3 2 1

bottle 925 = 1 1 1 0 0 1 1 1 0 1

It would be sipped by prisioners marked 10,9,8,5,4 ,3 and 1 and they will die. After four weeks, line the prisoners up in their bit order and read each living prisoner as a 0 bit and each dead prisoner as a 1 bit. The number that you get is the bottle of wine that was poisoned.

1000 is less than 1024 (2^10). If there were 1024 or more bottles of wine it would take more than 10 prisoners.