Famous People Mumbles #14




Hint: has been dead for some time now.

Thousand Bottles, Revisited

Thousand bottles of wine puzzle can be analyzed in terms of information content. In the original puzzle, there is one bottle of poison amongst n = 2**m bottles of wine, and so the solution space is of size n, since  the answer can be any number from 0 to n-1.

Each prisoner yields only a single bit of information – by staying alive or dying. Hence at least m prisoners (or m bits) would be required to find the solution within the solution space of size 2**m.

Now, in the variation #1 posted earlier (https://dmranade.wordpress.com/2010/09/28/thousand-bottles-of-wine/), there are two unknowns: the poison and the antidote. There are n(n-1) possible solutions, so the information required to describe the answer is lg(n(n-1)) … almost 2m bits. Hence at least 2m prisoners would be required. Indeed, I know a solution using 2m prisoners that requires detecting the antidote in the first step and then removing that bottle, thus reducing the problem to the original 1000 bottle problem.

Now consider that there is an additional piece of information in variation no #1; half a vial of the pure poison has been recovered from the assassin. What if this vial was not available? That leads to another variation:

variation #2

All we know is that out of thousand bottles one bottle is poisoned and another one spiked with the antidote. We do have two days as before, i.e., result of one set of tests can be used in a second set of tests.

How many prisoners should suffice to solve this variation? The same argument as used for variation #1 should apply, hence 2m prisoners should be sufficient.

Here, however,  a solution with 2m prisoners is not known to me, although I did find an elegant solution using 3m-1 prisoners.

Famous People Mumbles #13