Fog Creek Software
Discussion Board




The Bad King Part II

Original riddle and solution reference:
****
http://www.techinterview.org/Solutions/fog0000000104.html
******

So after coming upon this riddle of this site, I took it to my psychology prof. at Univ. of Texas at Austin (who loves riddles and opted to stay anonymous), and he solved the riddle using only 4 prisoners and came up with a general solution for any amount of wine (all without using information theory and binary guesses). I liked his solution so much that I wanted to post his alternative answer. He agreed, but under the condition that I post this own version the riddle instead:

"After successfully finding the bottle, the bad king has his banquet and even buys another 1400 bottles of different wine to make his total collection come to 2400 bottles. However, the ever persistent neighboring queen sends another servant to poison the bottles with the same exact posion used last time--that is, it's potency is so high that it cannot be diluted and it kills in exactly 4 weeks. And again, the king's guards discover him before after he poisons only one bottle. He needs to find the bottle because he is throwing another banquet in 5 weeks time. However, the king only has 4 prisoners left in his dungeons. How would he go about finding the poisoned bottle using only 4 prisoners?"

Because I didn't how to post new riddles on this site, I just posted it here on the discussion forum. I apologize to the admin if I've broken any rules (admin--email me if you want the solution).

Tim Hsu
Friday, September 10, 2004

Off the top of my head, my answer would depend on which of the prisoners as well as when do they die.
The point is the king has one extra week, so we can use that too, and knowing that the poision takes exactly 4 weeks we could draw some pretty useful conclusion judging by when each prisoner dies.
So having 4 prisoners and 7 days to make them drink from different bottles we can use a number system to the base 7 instead of the binary we used earlier, and we can use number of up to 4 digits (the 4 prisoners)
And it just happens that the maximum number you can write in 4 digits of a base 7 number system is 2400 :)
The whole point is instead of depending on just the fact of whether a prisoner dies or not (1 or 0) we now use the fact of on which day he dies of the last week and hence the digits 0-6
So now bottle #1 would be 0000
bottle #2 0001
bottle #6 0006
bottle #7 0010
and bottle #2400 6666
for each digit u assign a prisoner and you have him drink from the bottle in the assigned day in his digit.
so for example for bottle #6 the first prisoner drink from it on the 6th day
and by the end of the 5 weeks period you can tell which bottle was poisoned by looking at the exact dies each of the 4 prisoners died.
It is worth mentioning that most probably all prisoners will die with this approach, but they're 4 anyway and the king obviously doesn't care ;)

Christian Kamel
Saturday, September 11, 2004

*  Recent Topics

*  Fog Creek Home