Question:

A bad king has a cellar of 1000 bottles of delightful and very expensive wine. A neighbor queen plots to kill the bad king and send a servant to poison the wine.

Fortunately (or say, unfortunately) the bad king’s guards catch the servant after he could poison only 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 bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king, he knows that he needs to murder no more than 10 prisoners – believing he can fob off such a low death rate – and will still be able to drink the rest of the wine (999 bottles) at his wedding party in 5 weeks time.

Explain what is in mind of the king, how will he be able to do so? (he has only 10 prisoners in his prisons)

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution:

The number the bottles are 1 to 1000. Now, write the number in binary format. We can write it as:

bottle 1 = 0000000001 (10 digit binary)

bottle 2 = 0000000010

.

.

.

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. And, this process will continue for every prisoner until the last prisoner is reached. For example:

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

Bottle 924 = 1 1 1 0 0 1 1 1 0 0

For instance, bottle no. 924 would be sipped by 10,9,8,5,4 and 3. That way if bottle no. 924 was the poisoned one, only those prisoners would 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. We know, 1000 is less than 1024 (2^10). Therefore, if there were 1024 or more bottles of wine it would take more than 10 prisoners.