In celebration of our king finding the village that was cheating him he decides to throw a celebration for the other 9 villages. In preparation for the celebration he orders 1000 barrels of the finest wine.
When the members of the uninvited village find out about the party they send an assassin to poison one of the barrels of wine. The poison takes 7 days to kill so the party guests won't realize what is happening for awhile.
However, after poisoning a random barrel the king's guard finds out and has the assassin executed. There is no time to order more wine so the king devises a genius plan to have his 10 loyal servants taste test the wine to find the poisoned barrel just in time for the party in 10 days. What is the plan that he devises so that he is left with 999 barrels of wine for the party?
I'd like to present a number of solutions, each one a little bit more optimized to save the lives of as many servants as possible.
- ###Solution 1: Binary Digits for numbers 0-999 Assign the numbers 0-999 to the barrels, consider the binary representation of those numbers, use the servants as binary digits.
After 7 days, the number that corresponds to the dead servants' digits points to the poisoned barrel.
####Analysis Now, this is a great solution. It's simple yet elegant, and solves the problem with time to spare. However, we'd like to optimize for lives saved, and there's definitely room for improvement on that front! In one of the worst cases – of which there are 5 (barrels #511, #767, #895, #959, #991) – 9 of our servants die. In 36 other cases, 8 servants will die. (Full distribution of deaths, starting with zero deaths: [ 1, 10, 45, 120, 210, 252, 208, 113, 36, 5 ] ).
Let's try to get those numbers down!
- ###Solution 2: Using all the days! Disclaimer: I will assume that the servants have 4 days to sample the barrels, since the time limit is arbitrary anyway. This simplifies some partitions and numbers, conveying the ideas easily. If they really only have 3 days, the same ideas can be applied, albeit with some odd numbers and possible remainders.
A simple way to reduce the number of potentially dead servants is to reduce the number of barrels. However, we have to test all 1000 barrels, so we're stuck here.
Or are we? We could let our servants test only 250 barrels on the first day. So, we number the barrels 0-249, and use Solution 1. If we have dead servants 7 days later, we can identify the barrel just as in Solution 1 using binary digits.
On the second day, the servants test the second batch of 250 barrels. This time, we label those barrels 1-250. If we have dead servants 7 days after this test, we know the poisoned barrel was in this second batch.
We do this with two more batches of 250 each on days 3 and 4, using labels 1-250. If no servant dies at all, we know the poisoned barrel was #0 of the first batch.
####Analysis This solution is better already! By effectively reducing the number of barrels we have to encode each time to 250, we only require 7 servants to begin with, and can send 3 home to their families right away. If the poisoned barrel is in the first batch, the distribution of deaths over the number 0-249 is [ 1, 8, 28, 56, 70, 56, 26, 5 ], giving us 5 out of 250 cases where 7 servants die. If the barrel is in one of the later batches with labels 1-250, we get [ 0, 8, 28, 56, 70, 56, 27, 5 ], meaning that at least one servant will die, but still we only kill 7 servants in the worst case.
- ###Solution 3: Pack those digits tight! Solution 2 looked pretty good, but it seemed odd that we would not make use of 3 servants. Somehow we should be able to improve our results by using all of our resources, right?
We will keep the batches of 250 barrels. But this time, instead of labeling them 0-249, we choose different labels. We will use:
- 0,
- 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,
- 3, 5, 9, 17, 33, 65, 129, 257, 513, 6, 10, 18, 34, 66, 130, 258, 514, …
Now, why those magic numbers, and where do they come from?
Why: We select our numbers from the range 0-1023 (inclusive) so that the binary representation of a number uses as few 1-digits as possible. There's one number with zero 1-digits. There are 10 numbers with exactly one 1-digit. There are 45 numbers with exactly two 1-digits, …
In general, there are 10!/(k!(10-k)!) numbers with exactly k 1-digits. A quick calculation shows us that we can easily cover 250 barrels with numbers having at most four 1-digits!
####Analysis Some of our servants might feel ambivalent about this solution. Because with this approach, we don't send anyone home right away. For our own benevolent purposes however, this solution is great!
In the worst case, only 4 servants will die, and we even get to minimize the number of those cases in our Distribution Of Death!
For the first batch, where we can use the 0, we get a DoD of [1, 10, 45, 120, 74], meaning that in 74 out of 250 cases, 4 servants will die.
For the subsequent 3 batches, we get a DoD each of [0, 10, 45, 120, 75].
###Epilogue This is as good as it gets for this line of thinking. For 4 Days of Potential Death and 10 Willing Testers, we get a worst case of 4 deaths, with an overall distribution as outlined in the analysis above.
The number of days do matter, as do the number of servants.
Extremes:
- We could have 999 servants. Each servant would sample exactly one barrel, and after 7 days, either:
- the dead servant corresponds to the poisoned barrel, or
- nobody dies, and the unsampled barrel is the poisoned one.
- We have 1006 days to find the poisoned barrel. One servant could sample one of 999 of the 1000 barrels each day, and
- if he dies, we know the poisoned barrel was the one he tested 7 days earlier, or
- if he lives, we know the poisoned barrel was the one he did not test at all.
I'm sure those factors could be optimized for expectation of survival for the individual servants.
If someone can come up with a solution that uses even less than 4 servants in the worst case, or if I have made mistakes, I'd love to hear them!