| easy | strategy |
So there's this king. Someone breaks into his wine cellar 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 to see which one he poisoned or to catch him.
The king needs the remaining 999 safe bottles for his party in 4 weeks. The king has 10 prisoners who deserve execution. The poison takes about 3 weeks to take effect, and any amount of it will kill whoever drinks it. How can he figure out which bottle was poisoned in time for the party?
Convert to binary strings?
The king has to mix wine in order to isolate the single poisoned one. 2) There are 10 servants. After about 3 weeks, each one can be either dead or alive, meaning that there are 2^10 = 1024 possible outcomes. Since 1024 > 1000, it's actually possible for some scheme to work.
Here's the scheme: The king assigns each servant a number from 1-10. The king assigns each bottle a number from 0-999. When he labels them, though, he writes the number on the bottle in binary with ten digits, like this: 0: 000000000 1: 000000001 2: 000000010 3: 000000011 4: 000000100 5: 000000101 ... 999: 1111100111 and so on.
Now the strategy is simple: Pick bottle 1, write its binary form, look at the positions where '1' appears (here: 1st only). Make the corresponding prisoner drink small quantitiy of that wine. (ie prisoner 1 takes a sip of wine #1). Continue this process upto 1000th wine. After 3 weeks, suppose only prisoner number 4 & 7 die. This means the binary representation of poisoned wine has '1' at position 4 & 7, and rest all zeros. Convert this binary number to decimal and that gives the poisoned wine.