ChapterZero

I was looking for information on the Fejer kernel earlier, and came across a wonderful explication at william wu’s website. I also came across this problem:

An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king’s guards catch the servant after he has only poisoned one bottle. The guards don’t know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?

And, what is the probability that under this scheme a given prisoner will die?

Read on for my solution

If the king takes all possible subgroups of the 10 prisoners and lets each subgroup drink from a different bottle of wine, all in the prisoners in exactly one subgroup will die, and the poisoned bottle will be located. Since the number of subgroups is $2^{10}=1024$, the king has just enough prisoners for this evil scheme to work.

I think the probability that a given prisoner will die is 1/2, because that’s the chance that they’ll be in a randomly selected subgroup.

Possibly relevant posts:

• Boundedness of products of certain matrices (10/29/2007)
• Lost in Bandrika (8/23/2007)
• Tunnel-vision (1/28/2007)