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 poisened 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 prisioners 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 ans six have to drink the wine. After less than four weeks, suppose only prisoner 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.

Previous Question Next Question

Back to Course