A ruthless king has a cellar of 1,000 bottles of very expensive wine. An assassin infiltrates the wine cellar to poison the wine. Fortunately the king’s guards catch the plotter after she has poisoned only one bottle. Unfortunately, the guards don’t know which one of the bottles is poisoned. The poison is so strong that no amount of dilution will make it safe to drink. Furthermore, it takes one month to have an effect. The ruthlessking decides he will get some of the prisoners in his vast dungeons to test the wine. Being an intelligent, if ruthless, king, he knows he needs to sacrifice fewer than 10 prisoners and know for a certainty which one of the wine bottles was poisoned. How does he know that?
Hint: If there were 1,024 or more bottles of wine, it would take more
than 10 prisoners.
The solution to this puzzle should be familiar to any programmer:
Number the bottles 1 to 1,000, and write the number in binary
Bottle 1 = 0000000001
Bottle 250 = 0011111010
Bottle 1,000 = 1111101000
Now take prisoners 1 through 10 and let prisoner 1 take a sip from
every bottle that has a 1 in its least significant bit. Let prisoner 2
take a sip from every bottle with a 1 in the next most significant
digit. And so on until prisoner 10 takes a sip from every bottle with
a 1 in its most significant bit. For example, take bottle 924:
Bottle 924 1 1 1 0 0 1 1 1 0 0
Prisoner 10 9 8 7 6 5 4 3 2 1
In other words, bottle 924 would be sipped by prisoners 10, 9, 8,
5, 4, and 3. That way if bottle 924 was the poisoned one, only those
prisoners would die. After four weeks, the king lines the prisoners up
in their bit order. In effect, the king reads each living prisoner as a
0 bit and each dead prisoner as a 1 bit. The number that the king
derives from this strategy identifies the bottle of wine that was
Further, if the king really wanted to kill the least number
of prisoners (and assuming he had a lot of prisoners at his disposal), the best strategy is to let 999 prisoners each take a sip from their respective bottle. That way, only the prisoner sampling from the poisoned bottle would die.
Post your Comments below...
Comment Form is loading comments...