Question:

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 ruthless king 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?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution: The solution to this puzzle should be familiar to any programmer:

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

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 poisoned.

Extra credit: Mention that 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.