The King of a small country invites 1000 senators to his annual party. As gifts, each senator brings the King a bottle of wine, for a grand total of 1000 bottles of wine. Each bottle is signed by the senator who gave it.
At the end of the party, the Queen tells the King that one of the senators is trying to assassinate him, and has put deadly poison in the bottle of wine he gave as a gift. Unfortunately, the Queen doesn't know which senator is the traitor (and thus doesn't know which bottle of wine has the poison in it).
The King has 10 servants. He views them as expendable, and does not care if they live or die. He decides to use them to figure out which bottle is poisoned, which will then indicate which senator is trying to assassinate him.
His plan is to make each servant drink from zero or more of the bottles of wine. The King knows that the poison is such that if a servant drinks it, he will feel fine until noon on the next day, at which point he will instantly drop dead.
The King must know for sure who the traitor is by noon on the day after the party, or else the traitor will try to find another way to assassinate him. This essentially means that he has one shot to make his servants drink the wine in order to figure out which is the poison wine.
Note that the King can make any of the servants drink from any of the wine bottles. He does not need to make all of the servants drink wine if he doesn't want to. Any servant who drinks from the poisoned bottle will die the next day at noon.
How can the King figure out for sure who the traitor is by noon on the following day?
The insight is to see that you can have a unique set of servants drink each bottle of wine. Since you have 10 servants, there are 2^10 = 1024 unique ways to choose a set of servants. And if each wine has a unique set of servants who drinks it, then you will know exactly which bottle of wine is poisoned because the servants who drank it will die, and the servants who didn't drink it won't die.
ReplyDeleteSo we'll number each bottle from 1 to 1000. Then, to decide who will drink each bottle, we'll take the binary representation of the bottle number, and use it to determine who drinks it.
As an example, consider bottle 433. The 10-digit binary representation of 433 is "0110110001". This indicates that Servant 2, Servant 3, Servant 5, Servant 6, and Servant 10 should drink from this bottle (since the 2nd, 3rd, 5th, 6th and 10th digits of "0110110001" are 1's).
So the King just gets his servants to drink the different wines according to this process.The next day at noon, he will look at the exact set of servants that die. He will then consult the chart again, and the wine that was drunk only by the servants who died was the one with poison in it.