Poisoned Wine (Extension)

Before the king gets to administer the bottles of wine to the prisoners, an advisor stops him. He says that if more than 8 prisoners die, the townspeople might get angry and revolt. How can the king administer the wine so that no more than 8 prisoners die?

Hint

You still need 10 prisoners. Look at the binary representations that would cause 9 or 10 prisoners to die.

Solution

Answer: Relabel certain bottles to avoid binary numbers with 9 or 10 ones.

From the previous puzzle, we know that a minimum of 10 prisoners are needed to find the poisoned bottle. But let’s notice the following 10-digit binary numbers.

\begin{matrix} 0111111111_{2} & = 511 \\ 1011111111_{2} & = 767 \\ 1101111111_{2} & = 895 \\ 1110111111_{2} & = 959 \\ 1111011111_{2} & = 991 \\ 1111101111_{2} & = 1007 \\ 1111110111_{2} & = 1015 \\ 1111111011_{2} & = 1019 \\ 1111111101_{2} & = 1021 \\ 1111111110_{2} & = 1022 \\ 1111111111_{2} & = 1023 \end{matrix}

These are the only bottles of wine that are fed to 9 or 10 prisoners: 10 of these numbers would require that the corresponding bottle be administered to 9 prisoners, and 1 number requires all 10 prisoners.

Only 5 of our bottles (511, 767, 895, 959, and 991) are affected by this, so we can relabel them to another number that doesn’t break our new rule. A simple relabelling would be:
511 → 1001 (1111101001)
767 → 1002 (1111101010)
895 → 1003 (1111101011)
959 → 1004 (1111101100) 991 → 1005 (1111101101)

With this new strategy, the king can find the poisoned bottle, with at most 8 prisoners dying.

Previous puzzle in this series

Poisoned Wine

Try These Next

Unbiasing a Biased Coin

Complex Number Multiplication

Planting Trees 2