Re: [math-fun] poisoned wine bottles
I have no improvement to report on the 10-rat case, but here's a surprise development we owe to my former student Mike Quist. Shortly after I explained the poisoned bottle problem to him he pointed out that one shouldn't make the assumption that a uniform partition of the bottles is always going to be optimal. To prove his point, Mike constructed, for 7 rats, a 4-unique code of size 19. When the bottles are partitioned evenly this would give a discard fraction of 4/19, inferior to what one gets with Michael's size 21 4-unique code reported Nov. 28. However, by unequally partitioning the bottles you can get a discard fraction of 2/11 with Mike's code! Rather than show you Mike's code I'll give you the simplest case of this phenomenon which requires 6 rats. Using a mixed-integer program I checked that for less than 6 rats the equal partition is optimal. The same linear programming method found the following code for 6 rats: Construct the 2+2+2 product code from the 2-rat code {00,01,10}. This has 27 codewords. Now remove all the codewords of weight 3; that gives a code having 1 word of weight 0, 6 words of weight 1, and 12 words of weight 2, for a total of 19 codewords. Partition the wine bottles so 7/49 are assigned to the zero word, 1/49 to each of the weight 1 words, and 3/49 to each of the weight 2 words. You can check that for any union of codeword pairs you never have to discard more than the fraction 12/49 -- a modest improvement over 1/4. For example, there are some unions where 6 codewords are implicated (it is a 6-unique code), but in all these cases the bottle partition has the form (1+1+1+3+3+3)/49=12/49. Are unequal bottle partitions going to be the rule for optimal codes? So far we only know it is true for 6 and 7 rats. When I relax the equal partition condition and optimize the good codes we found in the past with respect to this I get no improvement (the optimal partition is the uniform one). So it seems we need a new approach to get the truly optimal codes. I can send the *.lp file for 7 or more rats to anyone interested with access to a big computer. At this point we only have optimal solutions up to 6 rats: n 1 2 3 4 5 6 f 1 2/3 1/2 2/5 1/3 12/49 The gurobi solver finds the last entry in 2 sec when I restrict the codewords to weight 2 and 15 minutes when I allow weight 3. For 7 rats it finds the 4/21 solution, that is optimal for weight < 3 , in 15 sec. But finding Quist's 2/11 solution, which includes weight 3, is not going to happen on my laptop! -Veit On Jan 6, 2013, at 4:46 PM, Veit Elser <ve10@cornell.edu> wrote:
Wow -- that was fast!
wax & wane has found several more 50/4's, all with the same (quaternion unit) symmetry group. I'll try a deeper search to see if something else turns up.
-Veit
Recall that the integer-programming approach giving unequal numbers of bottles for different codewords was proposed early on here by Thomas (on 11/20), who took as codewords all words of length 10 with weights 0, 1, 2, or 3, and having the number of rats assigned to each bin be 45, 13, 5, and 5, respectively. This is the optimal fully symmetric (that is, invariant under the full S_10 group acting on the rats) solution. If you don't constrain to integers, the fraction of bottles discarded is 40 / 397 (which would be a little over 100.75), and the fraction of rats assigned to codewords of each weight is 17/397, 5/397, 2/397, 2/397 respectively. So as to Veit's underlying question: this capped-union-codes approach is nice in that it's a computationally more-approachable restriction of the problem that seems to be doing pretty well, but I certainly don't see any reason to think that the optimal code should involve partitioning bottles close to uniformly among used codewords. --Michael On Sun, Jan 27, 2013 at 2:41 PM, Veit Elser <ve10@cornell.edu> wrote:
I have no improvement to report on the 10-rat case, but here's a surprise development we owe to my former student Mike Quist.
Shortly after I explained the poisoned bottle problem to him he pointed out that one shouldn't make the assumption that a uniform partition of the bottles is always going to be optimal. To prove his point, Mike constructed, for 7 rats, a 4-unique code of size 19. When the bottles are partitioned evenly this would give a discard fraction of 4/19, inferior to what one gets with Michael's size 21 4-unique code reported Nov. 28. However, by unequally partitioning the bottles you can get a discard fraction of 2/11 with Mike's code!
Rather than show you Mike's code I'll give you the simplest case of this phenomenon which requires 6 rats. Using a mixed-integer program I checked that for less than 6 rats the equal partition is optimal. The same linear programming method found the following code for 6 rats:
Construct the 2+2+2 product code from the 2-rat code {00,01,10}. This has 27 codewords. Now remove all the codewords of weight 3; that gives a code having 1 word of weight 0, 6 words of weight 1, and 12 words of weight 2, for a total of 19 codewords. Partition the wine bottles so 7/49 are assigned to the zero word, 1/49 to each of the weight 1 words, and 3/49 to each of the weight 2 words. You can check that for any union of codeword pairs you never have to discard more than the fraction 12/49 -- a modest improvement over 1/4. For example, there are some unions where 6 codewords are implicated (it is a 6-unique code), but in all these cases the bottle partition has the form (1+1+1+3+3+3)/49=12/49.
Are unequal bottle partitions going to be the rule for optimal codes? So far we only know it is true for 6 and 7 rats. When I relax the equal partition condition and optimize the good codes we found in the past with respect to this I get no improvement (the optimal partition is the uniform one). So it seems we need a new approach to get the truly optimal codes.
I can send the *.lp file for 7 or more rats to anyone interested with access to a big computer. At this point we only have optimal solutions up to 6 rats:
n 1 2 3 4 5 6 f 1 2/3 1/2 2/5 1/3 12/49
The gurobi solver finds the last entry in 2 sec when I restrict the codewords to weight 2 and 15 minutes when I allow weight 3. For 7 rats it finds the 4/21 solution, that is optimal for weight < 3 , in 15 sec. But finding Quist's 2/11 solution, which includes weight 3, is not going to happen on my laptop!
-Veit
On Jan 6, 2013, at 4:46 PM, Veit Elser <ve10@cornell.edu> wrote:
Wow -- that was fast!
wax & wane has found several more 50/4's, all with the same (quaternion unit) symmetry group. I'll try a deeper search to see if something else turns up.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Rats return! For the original problem (2 of 1000 poisoned, 10 rats) I'm still at discarding 80 bottles, but now I have two additional 80-bottle solutions to report. First, a brute-force search for capped union codes bore fruit. I looked for codes with symmetry dihedral of order 4 -- that is, if a word w is in the code, so are reverse(w) and cyclic_shift(w,5) -- and there are indeed some 50/4 codes of that form. Here's one, for posterity, representing the length-10 bit strings in decimal as usual: {3, 4, 9, 14, 18, 21, 24, 33, 39, 48, 66, 72, 77, 96, 106, 116, 128, 138, 145, 184, 210, 225, 258, 264, 278, 288, 300, 305, 323, 324, 344, 393, 418, 448, 513, 528, 540, 548, 553, 562, 576, 582, 593, 643, 672, 712, 768, 773, 778, 912} Second and more interestingly is Veit's mixed integer programming representation, which I've been playing with a bit. As Veit reported earlier, solvers like Gurobi can rapidly dispatch sufficiently small cases, so for starters I ran through the various numbers of rats restricted to codewords of weight up to 2 (= at most 2 rats drink from any bottle). Veit already reported the 12/49 fraction for n=6 rats (which turns out to be optimal even without the weight constraint) and 4/21 for n=7. For n=8, 9, 10 the best fractions are 2/13, 12/97, and 4/39 respectively. Interestingly, all solutions have the property that codewords with the same weight always get the same fraction of wine bottles. I'm trying to run the solver on n=7 and max_weight=3, the case where Veit reported on Mike Quist's 2/11 solution. That solution is the incumbent (best-so-far) but there's a ways to go for showing optimality. But as always, I'm looking at the 10-rat case, where even weight=3 seems way out of reach. So I decided to try the same trick as before, restricting to solutions with a reasonably large symmetry group. And it paid off! Restricting to codes with n=10, max_weight=4 and 10-fold cyclic symmetry, Gurobi was able to find the optimal solution, which again involved throwing away 80 (aka 8/100 of the) bottles: * Any pair of rats that is a cyclic shift of 0000000011, 0000000101, 0000001001, or 0000010001 -- that is, all pairs except (i, i+5) -- drinks from 1/100 of the bottles. * Any four-tuples of rats that is a cyclic shift of 0001000111 or 0000101101 drink from 3/100 of the bottles. This makes me happy, as it's the first 80-bottle solution sufficiently symmetric that I can carry it around in my head. --Michael PS: I wish we had any movement at all on a lower bound. The gap between 80 and the information-theoretic lower bound of 32 is vast. On Sun, Jan 27, 2013 at 2:41 PM, Veit Elser <ve10@cornell.edu> wrote:
I have no improvement to report on the 10-rat case, but here's a surprise development we owe to my former student Mike Quist.
Shortly after I explained the poisoned bottle problem to him he pointed out that one shouldn't make the assumption that a uniform partition of the bottles is always going to be optimal. To prove his point, Mike constructed, for 7 rats, a 4-unique code of size 19. When the bottles are partitioned evenly this would give a discard fraction of 4/19, inferior to what one gets with Michael's size 21 4-unique code reported Nov. 28. However, by unequally partitioning the bottles you can get a discard fraction of 2/11 with Mike's code!
Rather than show you Mike's code I'll give you the simplest case of this phenomenon which requires 6 rats. Using a mixed-integer program I checked that for less than 6 rats the equal partition is optimal. The same linear programming method found the following code for 6 rats:
Construct the 2+2+2 product code from the 2-rat code {00,01,10}. This has 27 codewords. Now remove all the codewords of weight 3; that gives a code having 1 word of weight 0, 6 words of weight 1, and 12 words of weight 2, for a total of 19 codewords. Partition the wine bottles so 7/49 are assigned to the zero word, 1/49 to each of the weight 1 words, and 3/49 to each of the weight 2 words. You can check that for any union of codeword pairs you never have to discard more than the fraction 12/49 -- a modest improvement over 1/4. For example, there are some unions where 6 codewords are implicated (it is a 6-unique code), but in all these cases the bottle partition has the form (1+1+1+3+3+3)/49=12/49.
Are unequal bottle partitions going to be the rule for optimal codes? So far we only know it is true for 6 and 7 rats. When I relax the equal partition condition and optimize the good codes we found in the past with respect to this I get no improvement (the optimal partition is the uniform one). So it seems we need a new approach to get the truly optimal codes.
I can send the *.lp file for 7 or more rats to anyone interested with access to a big computer. At this point we only have optimal solutions up to 6 rats:
n 1 2 3 4 5 6 f 1 2/3 1/2 2/5 1/3 12/49
The gurobi solver finds the last entry in 2 sec when I restrict the codewords to weight 2 and 15 minutes when I allow weight 3. For 7 rats it finds the 4/21 solution, that is optimal for weight < 3 , in 15 sec. But finding Quist's 2/11 solution, which includes weight 3, is not going to happen on my laptop!
-Veit
On Jan 6, 2013, at 4:46 PM, Veit Elser <ve10@cornell.edu> wrote:
Wow -- that was fast!
wax & wane has found several more 50/4's, all with the same (quaternion unit) symmetry group. I'll try a deeper search to see if something else turns up.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
On Mar 17, 2013, at 9:44 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Rats return! For the original problem (2 of 1000 poisoned, 10 rats) I'm still at discarding 80 bottles, but now I have two additional 80-bottle solutions to report.
Thanks for these new 8% solutions! I noticed that your first code, for equal wine bottle partitions, has a larger symmetry group than the one in which you searched. It's of order 16 and has a nice relationship to Pauli matrices. Here's the correspondence: {2, 5, 3, 1, 4, 9, 6, 8, 10, 7} = I Px {10, 9, 3, 7, 6, 1, 2, 8, 4, 5} = I Py {7, 10, 3, 6, 9, 2, 5, 8, 1, 4} = I Pz The permutations refer to the bits of your code, I = sqrt(-1), and Px, Py, Pz are the standard Pauli matrices. These generate the quaternion group of order 8 and act on the code exactly as all the 4/50 codes I found with the wax-and-wane algorithm (which assumed no symmetry). But your new code's symmetry also includes the generator {2, 5, 8, 1, 4, 7, 10, 3, 6, 9} = I This exchanges 3 and 8, unlike the others which keep these bits fixed; the corresponding 2x2 matrix is sqrt(-1) times the identity. You may have found the most symmetric 8% solution! It was a great idea to adapt the mixed-integer programming so it acts on symmetry orbits; n>7 is clearly out of reach otherwise. But you must feel frustrated that the best so far just ties the equal-partition result! You might try the slightly smaller quaternion group instead of the group of 10 cyclic shifts. -Veit
First, a brute-force search for capped union codes bore fruit. I looked for codes with symmetry dihedral of order 4 -- that is, if a word w is in the code, so are reverse(w) and cyclic_shift(w,5) -- and there are indeed some 50/4 codes of that form. Here's one, for posterity, representing the length-10 bit strings in decimal as usual:
{3, 4, 9, 14, 18, 21, 24, 33, 39, 48, 66, 72, 77, 96, 106, 116, 128, 138, 145, 184, 210, 225, 258, 264, 278, 288, 300, 305, 323, 324, 344, 393, 418, 448, 513, 528, 540, 548, 553, 562, 576, 582, 593, 643, 672, 712, 768, 773, 778, 912}
Second and more interestingly is Veit's mixed integer programming representation, which I've been playing with a bit. As Veit reported earlier, solvers like Gurobi can rapidly dispatch sufficiently small cases, so for starters I ran through the various numbers of rats restricted to codewords of weight up to 2 (= at most 2 rats drink from any bottle). Veit already reported the 12/49 fraction for n=6 rats (which turns out to be optimal even without the weight constraint) and 4/21 for n=7. For n=8, 9, 10 the best fractions are 2/13, 12/97, and 4/39 respectively. Interestingly, all solutions have the property that codewords with the same weight always get the same fraction of wine bottles.
I'm trying to run the solver on n=7 and max_weight=3, the case where Veit reported on Mike Quist's 2/11 solution. That solution is the incumbent (best-so-far) but there's a ways to go for showing optimality.
But as always, I'm looking at the 10-rat case, where even weight=3 seems way out of reach. So I decided to try the same trick as before, restricting to solutions with a reasonably large symmetry group. And it paid off! Restricting to codes with n=10, max_weight=4 and 10-fold cyclic symmetry, Gurobi was able to find the optimal solution, which again involved throwing away 80 (aka 8/100 of the) bottles:
* Any pair of rats that is a cyclic shift of 0000000011, 0000000101, 0000001001, or 0000010001 -- that is, all pairs except (i, i+5) -- drinks from 1/100 of the bottles. * Any four-tuples of rats that is a cyclic shift of 0001000111 or 0000101101 drink from 3/100 of the bottles.
This makes me happy, as it's the first 80-bottle solution sufficiently symmetric that I can carry it around in my head.
--Michael
Thanks, Veit -- great observations, as always. I do indeed intend to try other symmetry groups, as time (both mine and the machine's) permits, and will report back on any better (or non-worse) results. --Michael On Mon, Mar 18, 2013 at 4:44 PM, Veit Elser <ve10@cornell.edu> wrote:
On Mar 17, 2013, at 9:44 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Rats return! For the original problem (2 of 1000 poisoned, 10 rats) I'm still at discarding 80 bottles, but now I have two additional 80-bottle solutions to report.
Thanks for these new 8% solutions! I noticed that your first code, for equal wine bottle partitions, has a larger symmetry group than the one in which you searched. It's of order 16 and has a nice relationship to Pauli matrices.
Here's the correspondence:
{2, 5, 3, 1, 4, 9, 6, 8, 10, 7} = I Px {10, 9, 3, 7, 6, 1, 2, 8, 4, 5} = I Py {7, 10, 3, 6, 9, 2, 5, 8, 1, 4} = I Pz
The permutations refer to the bits of your code, I = sqrt(-1), and Px, Py, Pz are the standard Pauli matrices. These generate the quaternion group of order 8 and act on the code exactly as all the 4/50 codes I found with the wax-and-wane algorithm (which assumed no symmetry). But your new code's symmetry also includes the generator
{2, 5, 8, 1, 4, 7, 10, 3, 6, 9} = I
This exchanges 3 and 8, unlike the others which keep these bits fixed; the corresponding 2x2 matrix is sqrt(-1) times the identity. You may have found the most symmetric 8% solution!
It was a great idea to adapt the mixed-integer programming so it acts on symmetry orbits; n>7 is clearly out of reach otherwise. But you must feel frustrated that the best so far just ties the equal-partition result! You might try the slightly smaller quaternion group instead of the group of 10 cyclic shifts.
-Veit
First, a brute-force search for capped union codes bore fruit. I looked for codes with symmetry dihedral of order 4 -- that is, if a word w is in the code, so are reverse(w) and cyclic_shift(w,5) -- and there are indeed some 50/4 codes of that form. Here's one, for posterity, representing
the
length-10 bit strings in decimal as usual:
{3, 4, 9, 14, 18, 21, 24, 33, 39, 48, 66, 72, 77, 96, 106, 116, 128, 138, 145, 184, 210, 225, 258, 264, 278, 288, 300, 305, 323, 324, 344, 393, 418, 448, 513, 528, 540, 548, 553, 562, 576, 582, 593, 643, 672, 712, 768, 773, 778, 912}
Second and more interestingly is Veit's mixed integer programming representation, which I've been playing with a bit. As Veit reported earlier, solvers like Gurobi can rapidly dispatch sufficiently small cases, so for starters I ran through the various numbers of rats restricted to codewords of weight up to 2 (= at most 2 rats drink from any bottle). Veit already reported the 12/49 fraction for n=6 rats (which turns out to be optimal even without the weight constraint) and 4/21 for n=7. For n=8, 9, 10 the best fractions are 2/13, 12/97, and 4/39 respectively. Interestingly, all solutions have the property that codewords with the same weight always get the same fraction of wine bottles.
I'm trying to run the solver on n=7 and max_weight=3, the case where Veit reported on Mike Quist's 2/11 solution. That solution is the incumbent (best-so-far) but there's a ways to go for showing optimality.
But as always, I'm looking at the 10-rat case, where even weight=3 seems way out of reach. So I decided to try the same trick as before, restricting to solutions with a reasonably large symmetry group. And it paid off! Restricting to codes with n=10, max_weight=4 and 10-fold cyclic symmetry, Gurobi was able to find the optimal solution, which again involved throwing away 80 (aka 8/100 of the) bottles:
* Any pair of rats that is a cyclic shift of 0000000011, 0000000101, 0000001001, or 0000010001 -- that is, all pairs except (i, i+5) -- drinks from 1/100 of the bottles. * Any four-tuples of rats that is a cyclic shift of 0001000111 or 0000101101 drink from 3/100 of the bottles.
This makes me happy, as it's the first 80-bottle solution sufficiently symmetric that I can carry it around in my head.
--Michael
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Hot off the presses: Mixed-integer programming imposing the Pauli symmetry group (of size 16, generators in Veit's last message) handed me a rats solution that involves throwing away 184/2349 ~= 0.0783312 < 0.08 of the bottles! Gurobi says this is optimal given the symmetry group. Raw solution, not even cleaned up by putting symmetry orbits together: 1: 7/783, 2: 7/783, 3: 5/261, 4: 7/1566, 8: 7/783, 9: 5/261, 10: 2/2349, 14: 53/4698, 16: 7/783, 17: 2/2349, 18: 5/261, 21: 53/4698, 24: 5/261, 32: 7/783, 42: 2/783, 45: 131/4698, 64: 7/783, 81: 2/783, 92: 131/4698, 96: 5/261, 102: 131/4698, 113: 47/2349, 128: 7/1566, 132: 4/87, 138: 53/4698, 145: 53/4698, 178: 131/4698, 195: 131/4698, 232: 131/4698, 256: 7/783, 263: 131/4698, 273: 2/783, 288: 5/261, 298: 47/2349, 308: 131/4698, 320: 2/2349, 321: 2/783, 324: 53/4698, 329: 47/2349, 336: 2/783, 338: 47/2349, 408: 131/4698, 417: 131/4698, 448: 53/4698, 512: 7/783, 522: 2/783, 534: 131/4698, 544: 2/2349, 546: 2/783, 547: 47/2349, 548: 53/4698, 552: 2/783, 568: 47/2349, 576: 5/261, 581: 131/4698, 586: 47/2349, 649: 131/4698, 672: 53/4698, 720: 131/4698, 768: 5/261, 780: 131/4698, 785: 47/2349, 898: 131/4698 --Michael On Mon, Mar 18, 2013 at 8:47 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
Thanks, Veit -- great observations, as always. I do indeed intend to try other symmetry groups, as time (both mine and the machine's) permits, and will report back on any better (or non-worse) results.
--Michael
On Mon, Mar 18, 2013 at 4:44 PM, Veit Elser <ve10@cornell.edu> wrote:
On Mar 17, 2013, at 9:44 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Rats return! For the original problem (2 of 1000 poisoned, 10 rats) I'm still at discarding 80 bottles, but now I have two additional 80-bottle solutions to report.
Thanks for these new 8% solutions! I noticed that your first code, for equal wine bottle partitions, has a larger symmetry group than the one in which you searched. It's of order 16 and has a nice relationship to Pauli matrices.
Here's the correspondence:
{2, 5, 3, 1, 4, 9, 6, 8, 10, 7} = I Px {10, 9, 3, 7, 6, 1, 2, 8, 4, 5} = I Py {7, 10, 3, 6, 9, 2, 5, 8, 1, 4} = I Pz
The permutations refer to the bits of your code, I = sqrt(-1), and Px, Py, Pz are the standard Pauli matrices. These generate the quaternion group of order 8 and act on the code exactly as all the 4/50 codes I found with the wax-and-wane algorithm (which assumed no symmetry). But your new code's symmetry also includes the generator
{2, 5, 8, 1, 4, 7, 10, 3, 6, 9} = I
This exchanges 3 and 8, unlike the others which keep these bits fixed; the corresponding 2x2 matrix is sqrt(-1) times the identity. You may have found the most symmetric 8% solution!
It was a great idea to adapt the mixed-integer programming so it acts on symmetry orbits; n>7 is clearly out of reach otherwise. But you must feel frustrated that the best so far just ties the equal-partition result! You might try the slightly smaller quaternion group instead of the group of 10 cyclic shifts.
-Veit
First, a brute-force search for capped union codes bore fruit. I looked for codes with symmetry dihedral of order 4 -- that is, if a word w is
in
the code, so are reverse(w) and cyclic_shift(w,5) -- and there are indeed some 50/4 codes of that form. Here's one, for posterity, representing the length-10 bit strings in decimal as usual:
{3, 4, 9, 14, 18, 21, 24, 33, 39, 48, 66, 72, 77, 96, 106, 116, 128, 138, 145, 184, 210, 225, 258, 264, 278, 288, 300, 305, 323, 324, 344, 393, 418, 448, 513, 528, 540, 548, 553, 562, 576, 582, 593, 643, 672, 712, 768, 773, 778, 912}
Second and more interestingly is Veit's mixed integer programming representation, which I've been playing with a bit. As Veit reported earlier, solvers like Gurobi can rapidly dispatch sufficiently small cases, so for starters I ran through the various numbers of rats restricted to codewords of weight up to 2 (= at most 2 rats drink from any bottle). Veit already reported the 12/49 fraction for n=6 rats (which turns out to be optimal even without the weight constraint) and 4/21 for n=7. For n=8, 9, 10 the best fractions are 2/13, 12/97, and 4/39 respectively. Interestingly, all solutions have the property that codewords with the same weight always get the same fraction of wine bottles.
I'm trying to run the solver on n=7 and max_weight=3, the case where Veit reported on Mike Quist's 2/11 solution. That solution is the incumbent (best-so-far) but there's a ways to go for showing optimality.
But as always, I'm looking at the 10-rat case, where even weight=3 seems way out of reach. So I decided to try the same trick as before, restricting to solutions with a reasonably large symmetry group. And it paid off! Restricting to codes with n=10, max_weight=4 and 10-fold cyclic symmetry, Gurobi was able to find the optimal solution, which again involved throwing away 80 (aka 8/100 of the) bottles:
* Any pair of rats that is a cyclic shift of 0000000011, 0000000101, 0000001001, or 0000010001 -- that is, all pairs except (i, i+5) -- drinks from 1/100 of the bottles. * Any four-tuples of rats that is a cyclic shift of 0001000111 or 0000101101 drink from 3/100 of the bottles.
This makes me happy, as it's the first 80-bottle solution sufficiently symmetric that I can carry it around in my head.
--Michael
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
-- Forewarned is worth an octopus in the bush.
participants (2)
-
Michael Kleber -
Veit Elser