[math-fun] poisoned wine bottle puzzle
Hello funsters, Somehow I've never seen this puzzle before! Is this old hat to any of you? You have 1000 bottles of wine, which you need for a party that starts in an hour. Two of the bottles are poisoned. You have ten rats, and you can cause each rat to drink from any subset of the bottles, which will cause it to die if the bottle is poisoned. But the poison takes most of an hour to act, so you only get one round of giving wine to rats, after which you must throw away any bottle which you do not know is safe. What do you do? I'd be happy to hear either worst-case or average-case results. Obviously if only one bottle were poisoned, you'd number the bottles and assign one rat to each bit of the binary representation, and the dead rats would spell out the binary of the unique poisoned bottle number. But two poisoned bottles seems to make this much more subtle. --Michael -- Forewarned is worth an octopus in the bush.
A slightly different version of the puzzle is when the party doesn't start for *two* hours. With one poisoned bottle, how many rats do you need to identify the poisoned bottle with certainty (easy, answer at the bottom of this email). With two poisoned bottles, I have no idea. The question "how many rats do you need to identify both poisoned bottles with certainty" seems to me a more natural problem, and more likely to have an interesting answer, than "what's the best you can do with 10 rats?" Andy On Thu, Nov 15, 2012 at 4:45 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Hello funsters,
Somehow I've never seen this puzzle before! Is this old hat to any of you?
You have 1000 bottles of wine, which you need for a party that starts in an hour. Two of the bottles are poisoned.
You have ten rats, and you can cause each rat to drink from any subset of the bottles, which will cause it to die if the bottle is poisoned. But the poison takes most of an hour to act, so you only get one round of giving wine to rats, after which you must throw away any bottle which you do not know is safe.
What do you do? I'd be happy to hear either worst-case or average-case results.
Obviously if only one bottle were poisoned, you'd number the bottles and assign one rat to each bit of the binary representation, and the dead rats would spell out the binary of the unique poisoned bottle number. But two poisoned bottles seems to make this much more subtle.
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Solution to the two-hour, one-poisoned-bottle version: 7 rats suffice. Number the bottles in ternary, not in binary. Assign one rat to each position: a zero means the rat doesn't drink from the bottle, a 1 means it drinks from the bottle in the first hour, a two means it drinks from the bottle in the second hour. -- Andy.Latto@pobox.com
I'm starting to see why we need so many bottles before this puzzle is interesting! We can bound the number of rejected bottles R by R <= 2 ceiling( 1000/M(10) ) where M(10) is the maximum size "perfect union code" on 10 symbols. I'm making up the name of these codes, which I believe are very interesting. Here's the definition: Describe binary codewords of length N in terms of subsets of N symbols. A "perfect union code" is a set of codewords such that if A, B, C are any distinct codewords in the code, then it never happens that A is contained in the union of B and C. The maximum sizes of perfect union codes starts out being very boring: M(3) = 3 M(4) = 4 M(5) = 5 M(6) = 6 These codes are just the N singleton subsets. But we can do better for large N using constant weight Hamming codes. The smallest example I know is for N=9. There is a binary code of weight 3 and distance 4 having size A(9,4,3)=12 (tables at http://www.win.tue.nl/~aeb/codes/Andw.html). It's easy to see that this code is a perfect union code. Since any two weight-3 codewords have distance 4, they can have at most a single symbol in common. Any third, distinct codeword can then have at most two symbols in common with their union, so it would not be contained in their union. Generalizing, M(N) >= A(N,2K+2,2K+1) K=0,1,2, … These codes give the following lower bounds: M(9) >= 12 M(10) >= 13 M(11) >= 17 M(12) >= 20 M(13) >= 26 M(14) >= 28 M(15) >= 42 M(16) >= 48 The bound on the 10-rat rejected bottle count is R <= 154. I haven't looked for the sequence M(3), M(4), … in OEIS because I'm uncertain exactly where M(N) first is greater than N. Using integer programming with glpk I can probably get M(7) but not higher. -Veit On Nov 15, 2012, at 4:45 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Hello funsters,
Somehow I've never seen this puzzle before! Is this old hat to any of you?
You have 1000 bottles of wine, which you need for a party that starts in an hour. Two of the bottles are poisoned.
You have ten rats, and you can cause each rat to drink from any subset of the bottles, which will cause it to die if the bottle is poisoned. But the poison takes most of an hour to act, so you only get one round of giving wine to rats, after which you must throw away any bottle which you do not know is safe.
What do you do? I'd be happy to hear either worst-case or average-case results.
Obviously if only one bottle were poisoned, you'd number the bottles and assign one rat to each bit of the binary representation, and the dead rats would spell out the binary of the unique poisoned bottle number. But two poisoned bottles seems to make this much more subtle.
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Andy Latto -
Michael Kleber -
Veit Elser