48 hours, and a prisoner will die 24 hours after drinking from the poisoned wine. you only need one prisoner, and a decent stopwatch. Have him drink from a barrel of wine every 6 minutes, watch the exact moment he dies. Take the time in minutes, divide by 6 and that's the wine barrel that's poisoned (zero indexed).
Is it really correct to interpret that as "dies in exactly 24 hours"?
Edit: My solution, which assumes that after tasting wine it could take any time between 0 and 24h to die; and that it could vary between tastings:
Given N slaves, you can test 2^N wines in a single iteration, as so:
- A set of size N has 2**N distinct sub-sets.
- Have each distinct sub-set taste a different wine.
- After 24h, everyone who drank the poisoned wine will be dead, and,
provided you took notes about which set consumed which wine, you
can look up which wine they drank.
- (Note also, you leave one wine untasted; if nobody dies, it is the
poisoned one.)
- The set with five slaves will taste a single wine.
- Sets with four slaves will taste 2 wines.
- Sets with three slaves will taste 4 wines.
- Sets with two slaves will taste 8 wines.
- Sets with one slave will taste 16 wines.
- We leave 32 wines untouched.
After 24 hours, all slaves who drank poisoned wine will be dead, and we will have the following possible states:
- One slave is dead. We know the 16 wines he drank, and we have 4
slaves left. As shown above, we can easily determine which of
the 16 wines is poisoned in a single iteration.
- N slaves are dead. We know which 2**(5-N) wines they drank, and
we have 5-N slaves left. So we can easily determine which of
the 2**(5-N) wines is poisoned in a single iteration.
So, we need to calculate how many wines we can test in this manner. Going through each set:
- 5 choose 1 * 16 = 80
- 5 choose 2 * 8 = 80
- 5 choose 3 * 4 = 40
- 5 choose 4 * 2 = 10
- The one wine that all slaves drink the first time.
- The 32 wines none of them drink the second time.
You label each barrel of wine with a 5 digit binary label. "But wait," you say "5 digits in binary can only enumerate 32 barrels from 00000 (0) to 11111 (31)." You are right, but I did not say the labels were unique.
There is only one barrel labeled 11111. For every barrel that has a label that has exactly one zero, there are two barrels carrying that label. This there are two barrels with the label 01111 and two more barrels labeled 10111, etc. For every label with exactly two zeros, there are four barrels having that same label.
In general, if a label has n zeros (0<=n<=5) there are 2^n barrels having that same label. Now lets see how many barrels we can label using this scheme.
There will be 2^5=32 barrels having the number 000000.
For numbers with 4 zeros there are 5 possible labels and 16 barrels per label. 5x16=80.
For barrels with 3 zeros, there are 5 choose 3 = 10 possible labels, and 2^3=8 barrels per label. 8x10 = 80 total barrels that can be labeled.
For barrels with 2 zeros, there 5 choose 2 = 10 possible labels again with 4 barrels per label. 10x4= 40 barrels.
And for barrels with one zero there are 5 possible labels with 2 barrels per label, which equals 10 barrels.
As mentioned before there is only one barrel that is labeled 11111.
So the grand total is 32+80+80+40+10+1=243 barrels. Thus we can label 243 barrels using the above described scheme. We label 240 barrels and throw away three labels.
Now we get to the slaves. We number the slaves from 1 to 5. Each slave number will be a significant position in a binary barrel label number. We take the slaves to each barrel, and look at the label for the barrel. The slaves whose numbers correspond to significant positions which have "1" on the barrels label drink. The slaves who correspond to significant positions which have "0" on the label don't drink. Thus, a label "10011" means that slaves number 1, 2 and 5 drink. A label "00100" means that only slave number 3 drinks.
After 24 hours we have 0-5 dead slaves. At this point we get a little sad and wonder why couldn't the problem have been worded in terms of rats, or something similar. But we keep on going; by the numbers of the dead slaves, we can determine which label is associated with the poisonous wine. The label with the poisonous wine is the one that has 1's in the positions associated with dead slaves. Thus if the first and second slave died, the poisonous label was 00011.
If all slaves died, it kind of sucks for them, but we are in luck - that means the poisonous label was 11111 and there is only one barrel with this label, so we know which was the poisonous barrel.
But if some slaves survived we will know the poisonous label but will have multiple barrels carrying this label.
The number of slaves surviving will be equal to the number of zeros in the poisonous label. That is because the number of dead slaves is equal to the number of ones in the poisonous label. As discussed above, the number of barrels carrying any label is equal to 2^n where n is the number of zeros in the label.
Thus, after 24 hours we are left with n slaves still living and 2^n barrels that are still suspicious (i.e., one of them is poisonous). If you have followed me thus far, solving this part will be trivial. We tear down the old labels and relabel the 2^n barrels with new n digit binary numbers. This time there is only one barrel per label. We also number the slaves from 1 to n to signify a significant position. We have each slave drink from each barrel that has a "1" in his significant position. And then we wait to see who dies. The poisonous barrel is the one whose label has "1" in every significant position associated with a dead slave.
Well, this is it, I hope you enjoyed it, and yes I am brilliant.
If 1 slave dies we have 16 suspect barrels Each remaining slave (4), pair (6), trio (4) and quartet (1) drink from 1 barrel - 15
If 2 slaves die we have 8 suspect barrels Each remaining slave (3), pair (3), and trio (1) drink from 1 barrel - 7
If 3 slaves die we have 4 suspect barrels Each remaining slave (2), pair (1) drink from 1 barrel - 3
If 4 slaves die we have 2 suspect barrels The remaining slave drinks from 1 barrel
If 5 slaves die we have a positive ID on the barrel
If 0 slaves die we have 9 suspect barrels Each remaining slave (5) and 3 pairs drink from 1 barrel - 8
My solution (which looks somewhat correct, so don't read unless you want it spoiled)
Day 0: Where all numbers are base 6 (240 in base 6 == 104)
d0 = last digit of barrel number (in base 6) d1 = second last digit of barrel number (in base 6)
Servant 0: drink if d0 == 0 or d1 == 0 Servant 1: drink if d0 == 1 or d1 == 1 Servant 2: drink if d0 == 2 or d1 == 2 Servant 3: drink if d0 == 3 or d1 == 3 Servant 4: drink if d0 == 4 or d1 == 4
At the end of the day, we will have at least 3 servants alive. (i.e. a maximum of 2 can die)
We now have 3 cases, depending on how many actually died:
- If no servants die, then d1 == 5, d2 == 5. It is barrel 55 (in base 6)
- If servant N dies, then d1 == N, d2 == 5 or d1 == 5, d2 == N. (note that the maximum barrel number is 104, so we can't have confusion between 105 and 5). So we have only two possibilities to test, which is easy with 3 servants alive.
- If servants N1 and N2 die, then d1 == N1, d2 == N2 or d1 == N2, d2 == N1. This gives us at most 4 possible barrels that could be poisoned [1,N1,N2], [1,N2,N1], [0,N1,N2], [0,N2,N1].
So at the end of day 1, we have at least 3 servants, and at most 4 possibilities to test for. Assign possibility 0, 1, 2 to remaining servants. If they all survive, then untested possibility is poisoned. Otherwise, it is obvious.
Edit: Here's my hint to those who have trouble solving this puzzle. Don't read it before trying to solve yourself!
(quite detailed, believe me explaining the approach in words was hard.)