A King, 1000 Bottles of Wine, 10 Prisoners and a Drop of Poison
a mathematical riddle
Ready for the solution?
Here’s the riddle we were looking at in the last lesson in case you missed it.
The King of a small country invites 1000 senators to his annual party. As a tradition, each senator brings the King a bottle of wine. Soon after, the Queen discovers that one of the senators is trying to assassinate the King by giving him a bottle of poisoned wine. Unfortunately, they do not know which senator, nor which bottle of wine is poisoned, and the poison is completely indiscernible. However, the King has 10 prisoners he plans to execute. He decides to use them as taste testers to determine which bottle of wine contains the poison. The poison when taken has no effect on the prisoner until exactly 24 hours later when the infected prisoner suddenly dies. The King needs to determine which bottle of wine is poisoned by tomorrow so that the festivities can continue as planned. Hence he only has time for one round of testing. How can the King administer the wine to the prisoners to ensure that 24 hours from now he is guaranteed to have found the poisoned wine bottle?
Don’t worry if you weren’t able to solve it. The important part is to try.
If you’re still working on this, you might find this article helpful!
I have two possible solutions for you: my solution and my boyfriend’s solution. Essentially they are the same end result, but take slightly different approaches.
possible solution one:
Let’s start by restating the problem.
We have 1000 bottles of wine, one of which is poisoned and somehow we need to test all of the wine bottles using only 10 prisoners as taste testers. However we decide to administer the wine to the prisoners, we need to use the prisoners deaths as a code to trace back to the poisoned wine bottle.
Since we have only 24 hours to test the wine, we know that there is not enough time nor enough prisoners to test the wine one-by-one. I’m guessing you got to this point and that’s where the confusion set in.
How can we test all of the bottles? Well, we’re going to have to get the prisoners drunk, I can tell you that much! Jk, but seriously we need to systematically distribute the wine to the prisoners so that there are at least a thousand different combinations!
First, let’s line up our 10 prisoners and label them. Also label the wine bottles 0–999 so we can tell them apart.
Let’s have Prisoner A drink from every other bottle starting with the first bottle, bottle #0. In other words, Prisoner A will drink from bottles 0, 2, 4, …
Next, assign Prisoner B the task of drinking from every other set of two bottles. For example, Prisoner B drinks from bottles 0 and 1, skips 2 and 3. Drinks from 4 and 5, skips 6 and 7, and so forth continuing the pattern.
Have Prisoner C drink from every other set of four bottles: i.e. Prisoner C drinks from bottles 0–3, (skip 4–7), 8–11, (skip 12–15), 16–19, …
Are you seeing the pattern? Keep doubling the number of bottles each prisoner drinks in succession.
Prisoner D drinks from every other set of eight bottles. Prisoner E from every other set of 16. Prisoner F from every other 32. Prisoner G from every other 64. Prisoner H from every other 128. Prisoner I from every other 256. And lastly, Prisoner J from the first 512 bottles.
At this point, you may notice something looks familiar. The bottle assignments reflect powers of 2.
We have successfully distributed the wine so that there are sufficiently many combinations. Now we wait 24 hours to see which prisoners were poisoned.
How will we be able to tell which bottle was the poisonous one? We will look at the pattern of poisoned prisoners encoded in binary. To do so I’ll place a zero above the prisoners who are poisoned, and a one above those who aren’t.
Before we decode the result, we need to flip our prisoners around so that it matches the binary place-value system.
There we go. Now suppose all the prisoners are poisoned? Which bottle of wine was it?
Well it must have been the first bottle, bottle #0, since this is the only bottle that they all drank from.
This is confirmed in our diagram because if they are all poisoned, we place a zero above every prisoner. And 0000000000 in binary is still 0 in decimal.
Now let’s suppose that everyone except prisoner A is poisoned.
If we translate 0000000001 into decimal we get 1. Which means bottle # 1 was poisoned. This confirms what we know to be true because Prisoner A was the only prisoner not to drink from bottle # 1 (remember Prisoner A drank from bottles 0, 2, 4, 6…).
How about if prisoners J, H, F, D and B are poisoned?
Translate the number 0101010101 into decimal to determine which bottle it was.
101010101 = 256 + 64 + 16 + 4 + 1 = 341.
Hence, bottle number 341 was the poisonous bottle.
Pretty clever, isn’t it? Because there are 10 prisoners and each prisoner has two states (dead or alive), this system has a grand total of 1,024 different combinations.
This is more than enough combinations since we only have 1000 bottles.
possible solution two:
This solution jumps straight into binary.
To begin, label each bottle with both its decimal number and binary equivalent.
Now each bottle serves as a code describing which prisoners are to drink from it. In this system, a one means the prisoner drinks from it, a zero means the prisoner doesn’t.
For example, only Prisoner J should drink from bottle one since its binary is 0000000001. Whereas, Prisoners I and G should drink from bottle ten whose binary is 0000001010 because it has 1's in the columns that match up with prisoners I and G.
Continue this process until you have given out sips of wine from every bottle. After 24 hours, line up the prisoners in order and note which ones have been poisoned with ones and mark the rest with zeros. Convert this number back into decimal to reveal which bottle was poisoned.
Whew! Wasn’t that fun?!
Next Lesson: Your Calculator is Killing Your Math Skills
Thanks for reading!
Please click the ❤ to let me know you learned something new!
More Puzzling Problems
Today’s problem goes out to a special new member of the family. Welcome to the world my niece, Edison Grace Berry! My…medium.com