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