The King and the Poisoned Wine: An interesting Problem
I got introduced recently to an interesting math problem, (thanks to Srikumar Raman). The problem goes like this:
A king has an important party coming up where he intends to serve the wine from his cellars. There are 500 barrels of wine in all, but there is one problem. One of those barrels contains poisoned wine – even a drop of this wine will kill.
The king also has a prison which is full of people whose lives are expendable. It is one of the king's pastimes to use the prisoners for various experiments where their lives are put at risk.
Now for the problem on hand:
(The requirement in each case is to find the minimum number of prisoners needed to test the wine.)
Level 1
The poisoned wine will kill anytime within 24 hours, i.e. if any person consumes it, he will die sometime within that period. The king wants to test the wine using his prisoners so that he finds the poisoned barrel and keeps it aside for future use, this party not being one such intended use.
The party is to be held 24 hours from now.
How many prisoners are needed in all to test the wine? Your job is to minimise the number of prisoners needed to test the wine. It does not matter how many prisoners die in the experiment.
Solution to Level 1:
In case the party is to be held at an indefinite future date, then all you need is 1 prisoner. Every 24 hours, he is fed some wine from one of the barrels. He will eventually die of poisoning, and that particular barrel can be segregated.
However, we have only 24 hours. Since it does not matter how many prisoners die, we need to line up the required number of prisoners, and feed them a 'combination' of wines from identified barrels. For each barrel, the combination must be unique, for example, if Prisoners A,B,D, and E die, it will identify, say, Barrel 27, or some such.
How do we arrive at the most effective combinations to minimize the number of prisoners?
Assume there is only one prisoner. How many barrels can be tested? Two. You make him have the wine from Barrel 1. If he dies, that is the poisoned barrel; if he does not, Barrel 2 is the poisoned barrel.
Assume there are two prisoners. You can test four barrels. Prisoner A gets wine from Barrels 1 and 3. Prisoner B from Barrels 2 and 3. If only A dies, Barrel 1 is poisoned. If only B dies, Barrel 2 is poisoned. If A and B both die, Barrel 3 is poisoned. If none of them die, it is barrel 4 that is poisoned.
You get the idea. The most effective way of arriving at the combinations for 500 barrels is to number each of the barrels from 0 to 499 in binary. To write the numbers 0 and 1 in binary, you need one digit. To write 0 to 4, you need two digits, to write 0 to 8 three digits, 0 to 9 four digits and so on.
If there are n binary digits, we can write all the numbers from 0 to ((2 ^ n)-1)
You need nine binary digits to represent all numbers from 0 to 511, and hence, nine binary digits for the 500 barrels that will be numbered 0 to 499.
Pick 9 prisoners, label them A to I. A will represent the rightmost digit (2 ^ 0), B will represent the next digit from the right (2 ^ 1), and so on, till I, who will represent 2 ^ 8 = 256.
Like this:
| I | H | G | F | E | D | C | B | A |
| 2^8 | 2^7 | 2^6 | 2^5 | 2^4 | 2^3 | 2^2 | 2^1 | 2^0 |
| 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Taking a few barrels as an example, Barrel nos. 0,8,303 401 and 499 will be represented as follows in binary:
| | I | H | G | F | E | D | C | B | A |
| | 2^8 | 2^7 | 2^6 | 2^5 | 2^4 | 2^3 | 2^2 | 2^1 | 2^0 |
| | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| | | | | | | | | | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 303 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 401 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 499 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
Number all the barrels from 0 to 499 using the above binary scheme.
Make Prisoner A drink the wine from all barrels marked 1 in column A.
Make Prisoner B drink the wine from all barrels marked 1 in column B.
And so on…
At the end of 24 hours, if you find A,B,C,D,F and I dead, it is barrel no. 303 that contains the poison.
If Barrel No. 499 has the poison, all prisoners except C and D will die.
If no one dies it is of course barrel no. 1 that is poisoned, since that is the only barrel from which no one drank.
So, in order to test 500 barrels (actually any number upto 512 barrels) you need 9 prisoners.
The answer is, thus, nine prisoners.
(Thanks to Dilip Thosar for solution to Level 1)
Level 2
The party is 48 hours from now – other conditions remain the same. What is the minimum number of prisoners needed?
Solution to Level 2
There are two time periods available now. So you can divide the barrels into two lots of 250 each. For the above lot, applying the same binary system explained above, you will need 8 prisoners. If you find the poisoned barrel, fine; else, use the same 8 prisoners and repeat the experiment in period 2.
Now, 8 prisoners is a good solution, but not the best. Let us try for a better solution.
When one time period was available to test the barrels, we used the number system with base 2. Now let us try using the number system with base 3. If there are n digits, we can represent 3 ^ n numbers in base 3. Base 3 of course will only use the digits 0,1 and 2.
6 prisoners can represent 729 numbers, viz., all numbers from 0 to 728.
Number the barrels using the base 3 number system, like so:
| | F | E | D | C | B | A |
| | 3^5 | 3^4 | 3^3 | 3^2 | 3^1 | 3^0 |
| | 243 | 81 | 27 | 9 | 3 | 1 |
| | | | | | | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 2 | 2 |
| 303 | 1 | 0 | 2 | 0 | 2 | 0 |
| 401 | 1 | 1 | 2 | 2 | 1 | 2 |
| 499 | 2 | 0 | 0 | 1 | 1 | 1 |
For this example, let us assume Barrel No. 303 is poisoned.
In Period 1, let each prisoner drink wines from those barrels under his respective column that are marked "1".
In this case F will die. Mark a "1" under column F.
In Period 2, let each surviving prisoner drink wines from those barrels under his respective column that are marked "2".
Continuing the example, B and D will die. Mark "2" under those columns.
Put "0" in the unmarked columns, i.e. columns A, C and E.
You end up representing the number 303 in base 3. Thus, you have found the poisoned barrel.
And you need only 6 prisoners to do it.
Level 3
The party is 72 hours from now –
Solution to Level 3:
This time we have three testing periods, hence represent the barrels using Base 4 notation. You will need 5 prisoners to solve the problem for anywhere upto 1024 barrels.
So, 5 prisoners are enough.
Level 4
The party is any 24x 9 hours from now, i.e. nine testing periods are available.
Solution to Level 4:
Since we have nine testing periods, use the decimal numbering system, the one we are all familiar with. Three prisoners are enough to take care of upto 1000 barrels.
So, in case nine testing periods are available, three prisoners are enough.
Level 5
Back to Level 2, i.e. the party is 48 hours from now. But with a twist. The wine will kill anytime exactly between 23 and <less than 24> hours, i.e. it will kill in 23 hours and n minutes, n being less than 60.
Solution to Level 5:
Arrange the barrels in a grid of 23 rows and 23 columns. Since there are only 500 barrels, some slots will be empty, but that does not matter.
You need only two prisoners. Let prisoner A drink all wines in Row 1 in Hour 1, all wines in Row 2 in Hour 2, etc.
Let prisoner B drink all wines in Column 1 in Hour 1, all wines in Column 2 in Hour 2, etc.
Both will die. Depending on when exactly each of them dies, you can establish which barrel is poisoned.
(Thanks to Srikumar Raman for solution to Level 5) 
