No servants were harmed in the making of this puzzle March 24, 2012Posted by Ezra Resnick in Computer science, Puzzles.
Twelve hours before the Emperor’s great banquet is to begin, the Master of Spies comes forward with distressing news: there is good reason to suspect that (exactly) one of the 1024 barrels of wine in the imperial wine cellar has been poisoned. The poison believed to have been used is odorless and otherwise undetectable, but so deadly that drinking even a small amount is certain to cause death within twelve hours.
The Emperor is determined to identify the poisoned barrel before the banquet begins — but how? It occurs to him that he could have 1024 of his servants each take a sip from a different barrel, and see which one dies. However, there is much work to be done preparing for the banquet, so it would be preferable to minimize the number of drunk servants. How can the poisoned barrel be positively identified while utilizing the smallest possible number of servants? (Note that the Emperor doesn’t care how many servants end up dying, he just wants to minimize the number of servants drinking wine.)
Try to solve it yourself before reading on.
The problem can be solved using just ten servants. Each servant will drink from 512 barrels — half of them — but each servant will drink from a different combination of barrels, so that which servants end up dying will uniquely determine the poisoned barrel. We begin by lining up all the barrels and numbering them, 0 through 1023. Servant #0 will drink from every other barrel, meaning all the odd-numbered barrels: #1, #3, #5… up to #1023. Servant #1 will alternate by twos, drinking from barrels #2, #3, #6, #7, #10, #11, etc. Servant #3 will alternate by fours, drinking from barrels #4, #5, #6, #7, #12, #13, #14, #15, etc. Servant #4 will alternate by eights, servant #5 by sixteens — and so on, so that servant #9 skips the entire first half of the barrels (#0-511) and drinks from all the rest (#512-1023).
We then wait twelve hours and see who dies. Each of the ten servants either lives or dies, so there are 210 = 1024 possible outcomes, and each of them implicates a different barrel. If no one dies, the poisoned barrel must be #0, since it’s the only barrel no one drank from. If only servant #0 dies, the poisoned barrel must be #1, since it’s the only barrel that only servant #0 drank from. Similarly, If only servant #1 dies, the poisoned barrel must be #2. If servants #0 and #1 both die but all the rest live, the poisoned barrel is #3, since it’s the only barrel that servants #0 and #1 both drank from but no one else did. And so on: barrel #4 is implicated if only servant #2 dies, barrel #5 is implicated if servants #0 and #2 both die but the rest live, etc. If all ten of the servants die, the poisoned barrel is #1023, which is the only one they all drank from.
You may have noticed that what we’re actually doing here is counting in binary. Each of the servants is assigned a power of two (from 20 to 29), and hence corresponds to a unique position in a ten-digit binary number. If we look at the barrel numbers in binary, each servant drank from the barrels where his corresponding digit is 1 and skipped the barrels where his corresponding digit is 0. For instance, barrel #1 (0000000001 in binary) was tasted only by servant #0; barrel #2 (0000000010) was tasted only by servant #1; barrel #3 (0000000011) was tasted by both servants #0 and #1; and so on — up to barrel #1023 (1111111111) which was tasted by all the servants. To identify the poisoned barrel, we simply place a 0 in the position of every live servant and a 1 in the position of every dead one, and we get the (binary) number of the only barrel tasted by all of the dead and none of the living.
The Emperor’s banquet was a great success, by the way.