5The King of Walschovia ordered a grand banquet to celebrate the marriage of his daughter. He invited all the aristocracy of the neighboring kingdoms and ordered 1000 barrels of wine to serve the guests.

Unfortunately, a band of terrorists hatched a plot to poison the wine. A week before the banquet, they entered the wine cellar and managed to poison one of the 1000 barrels before they were caught. 10 terrorists were captured alive, but in the confusion, nobody remembered which barrel was poisoned.

There is now insufficient time to order more than a couple of new wine barrels. To preserve the prestige of the king, you must identify which of the 1000 barrels is poisoned. The lives of the 10 terrorists are forfeit so you can test any of the wine on them.

The poison is such that if a person drinks even a drop, he will die within a week, though it is impossible to predict when during the week he will die. The party is only a week away.

.

.

.

.

.

To fully appreciate the solution to this problem, it helps if you understand binary numbers. Don’t worry, its surprisingly easy to learn and is used in all computers.

Lets take a decimal number at random, say nine thousand five hundred forty six (9546). This can be written as the sum of nine thousands, five hundreds, four tens and six ones.

9546 = **9***1000 + **5***100 + **4***10 + **6***1

Or to put it another way

9546 = **9***10^{3} + **5***10^{2} + **4***10^{1} + **6***10^{0}

Note that I am using the fact that 10^{0} = 1

This is the way we write a decimal number and we do it so often we don’t even notice it. Similarly, when we write a binary number, we use 0s and 1s and interpret it in base 2. What this means is that if we take a number 10101 in binary, it can be read as

10101 = **1***2^{4} + **0***2^{3} + **1***2^{2} + **0***2^{1} + **1***2^{0}

Just start from the right going 1 digit at a time and multiplying with steadily increasing powers of 2. So 10101 becomes:

10101 = **1***2^{4} + **0***2^{3} + **1***2^{2} + **0***2^{1} + **1***2^{0} = 1*16 + 0*8 + 1*4 + 0*2 + 1 = 16 + 4 + 1 = 21

Lets try to read some more binary numbers

1111 = **1***2^{3} + **1***2^{2} + **1***2^{1} + **1***2^{0 }= 1*8 + 1*4 + 1*2 + 1 = 8 + 4 + 2 + 1 = 15

11 = **1***2^{1} + **1***2^{0 }= 1*2 + 1 = 2 + 1 = 3

101 = **1***2^{2} + **0***2^{1} + **1***2^{0 }= 1*4 + 0*2 + 1 = 4 + 0 + 1 = 5

We can even do this for much larger numbers

1011011101 = **1***2^{9} + **0***2^{8} + **1***2^{7} + **1***2^{6} + **0***2^{5} + **1***2^{4} + **1***2^{3} + **1***2^{2} + **0***2^{1} + **1***2^{0 }

= 1*512 + 0*256 + 1*128 + 1*64 + 0*32 + 1*16 + 1*8 + 1*4 + 0*2 + 1

= 512 + 128 + 64 + 16 + 8 + 4 + 1 = 753

Just like that any number can be written in binary.

Now, to the puzzle itself. Lets number all the barrels from 1 to 100. But we’ll write the numbers in binary. So we write

1 = 0000000001

2 = 0000000010

3 = 0000000011

4 = 0000000100

….

and so on.

Now see the right most digit. Take a drop from each of the barrels which have a 1 in the right most digit and give these drops to prisoner 1. This includes barrels marked:

000000000**1 **(1), 000000001**1 **(3), 000000010**1** (5), 000000011**1** (7) and so on. Essentially, the first prisoner is given a drop from all odd barrels. So if the 1^{st} prisoner dies, we know the poison must have come from an odd barrel. That already narrows us from having to worry about 1000 barrels to 500 barrels.

Now see the second from right digit. Take a drop from each barrel where the second from right digit is 1 and make the 2^{nd} prisoner drink these. So we get barrels 0000000010 (2), 0000000011 (3), 0000000110 (6), 0000000111 (7), 0000001010 (10), 0000001011 (11), and so on. Mathematically inclined may note that this represents the form 4n+2 and 4n+3. So if this prisoner dies, we know the poison must have been in one of these barrels.

Similarly, if we take the third from right digit and give the 3^{rd} prisoner a drop from the barrels where this digit is one and so on.

Finally, based on which prisoners die, we will know which bits to set to 1 and find out the number of the poisoned barrel.

For instance, if only the 7^{th}, 4^{th}, 3^{rd} and 1^{st} prisoners die, we know the poisoned barrel has a number with 1s in the 7^{th}, 4^{th}, 3^{rd} and 1^{st} position from the right or 0001001101 = **1***2^{6} + **1***2^{3} + **1***2^{2} + **1** = 64 + 8 + 4 + 1 = 77, the 77^{th} barrel is poisoned.