Someone breaks into the wine cellar of a king, where he stores 1000 bottles of wine. This person proceeds to poison one of the 1000 bottles, but gets away too quickly for the king's guard. Nobody knows which one he poisoned. The king needs the remaining 999 safe bottles for his party in four weeks. The king has ten prisoners who deserve execution. The poison takes just less than four weeks to take effect. Any amount of the poisoned wine will kill whoever drinks it.
How can he figure out which bottle was poisoned in time for the party?
Hint
Think about binary strings.
Answer
Since every prisoner can end up dead or alive, there are 2^10 = 1024 possible outcomes. Since 1024 > 1000, it's actually possible to use an approach using binary strings.
The king assigns each servant a number from 1 to 10.
The king assigns each bottle a number from 0 to 999.
When he labels them, he writes the number on the bottle in binary with ten digits, like this:
0: 000000000
1: 000000001
2: 000000010
3: 000000011
4: 000000100
...
999: 1111100111.
The strategy is simple: the king assigned the prissoners a number from 1 to 10, indicating the position of the number in the binary string. If the string has a number one on the - let's say - fifth- and sixth position, then the prisoners with number five and six have to drink the wine. After less than four weeks, suppose only prisoners number five and six die. This means the binary representation of poisoned wine has a '1' at position five and six, and the rest are all zeros.
Convert this binary number to a decimal and that gives you the number of the poisoned wine.
