# QUESTION 2

Long ago, before Japan was unified, a warlord invited commissioners from all over the country to gather for a great discussion. In total, 508 delegates from surrounding domains attended, and each brought a gift of sake for the warlord. On the eve of the great meeting one of the warlord’s spies discovered a plot to assassinate him: one of the bottles of sake was poisoned. However, the spy did not know which bottle it was.

The warlord was determined to discover which bottle had been poisoned, and thereby name the domain that was plotting against him. He would dramatically announce the perpetrator at the great meeting so that all of Japan would know of the plot.

However, the poison employed was undetectable. It has no smell or taste, does not alter the weight of the bottle, and even a tiny sip is deadly. It takes between 10 and 20 hours to kill a man.

The warlord planned to announce the plot in 24 hours. He decided to have some of his underlings drink the sake to determine which bottle contained the poison. What is the minimum number of underlings required to guarantee that the poisoned sake bottle is identified in time?

## QUESTION 2 is now closed! Wait for the next question to unlock or cut to the chase and buy DEAD SECRET on Steam!

Mouse over the text below for the solution:

The minimum number of underlings needed to **guarantee** identification of the poisoned sake is **nine**.

It might be possible to identify the poison with only one underling (if he is lucky enough to randomly select the right sake), but there’s no way to guarantee the bottle will be found with only one attempt. Similarly, methods that rely upon the poison killing an underling exactly ten hours after consumption do not work, as the poison *may* take as long as twenty hours to kill, depending on the individual. The warlord needs a method by which he is absolutely guaranteed to find the one poisoned bottle within 24 hours.

He starts by assigning each bottle a number. Bottle #1, Bottle #2, Bottle #3, etc, all the way up to Bottle #508. For each bottle he selects several underlings to take a sip. After 20 hours he checks which combination of underlings have died, and from this he can deduce the one bottle that was common between all of them.

To do this, he treats each underling like a *bit*, a value that can be 0 or 1, in this case alive or dead. Any number can be encoded as a collection of bits by treating each bit as a power of two. For example, Underling 0 represents 2^{0}, Underling 1 represents 2^{1}, Underling 2 represents 2^{2}, etc. To encode Bottle #9 we’d need 1 + 8 = 2^{1} + 2^{3}, so Underling 1 and Underling 3 would both take a sip of Bottle #9. If they both die and nobody else does, Bottle #9 must be poisoned.

In order to encode 508 unique combinations of underlings we need 9 bits (with 9 bits we can encode up values up to 511). For example, if the poisoned bottle is #367, that works out to 2^{0} + 2^{1} + 2^{2} + 2^{3} + 2^{5} + 2^{6} + 2^{8}, so we would expect underlings 0, 1, 2, 3, 5, 6, and 8 to die (as all of them drank from #367). Whatever the combination of underlings, death will come within 20 hours of sipping the sake, so as long as all of them take their various drinks at the same time the warlord will have plenty of time to make his announcement.

Back to Puzzles