Hi Scott, I've been looking over the muffin files, with an eye towards turning them into a paper. You mentioned that you had a 300 line C++ program to do some calculations. Could you send me a copy? Best, Victor On Sun, Mar 8, 2009 at 5:21 PM, Huddleston, Scott < scott.huddleston@intel.com> wrote:
I enclose examples of some of the bounds in my 28 Feb. post, and a derivation of the most involved example.
S(12/7) = 3/7 = r/4 = (3-r)/3
Muffins: 1/7 * { [3,4]*12 } Persons: 1/7 * { [4*3]*4, [3*4]*3 }
S(7/4) = 5/12 = (3-r)/3 = (2r-1)/6
Muffins: 1/12 * { [5,7]*6, [6*2] } Persons: 1/12 * { [5*3,6]*2, [7*3]*2 }
S(40/23) = 19/46 = (2r-1)/6 = (12-5r)/8
Muffins: 1/46 * { [19,27]*24, [20,26]*12, [23*2]*4 } Persons: 1/46 * { [19*3,23]*8, [20*4]*3, [27*2,26]*12 }
S(228/131) = 54/131 = (12-5r)/8 = (7r-6)/15
Muffins: 1/131 * { [54,77]*120, [55,76]*24, [57,74]*60, [65,66]*24 } Persons: 1/131 * { [54*3,66]*24, [54*2,55,65]*24, [57*4]*15, [77*2,74]*60, [76*3]*8 }
S(449/258) = 319/774 = (7r-6)/15 = (73-32r)/42
Muffins: 1/774 * { [319,455]*210, [320,454]*30, [325,449]*42, [336,438]*30, [337,437]*90, [384,398]*42, [387*2]*5 } Persons: 1/774 * { [319*3,390]*42, [319*2,325,384]*42, [320*3,387]*10, [336,337*3]*30, [455*2,437]*90, [455,454,438]*30, [449*3]*14 }
Here's a derivation of 449/258 example.
449 muffins -> 898 pieces, used in 124 4-parts with 496 pieces and 134 3-parts with 402 pieces.
We split muffins between a 3-part and a 4-part when possible, but 4-parts contain 94 more pieces than 3-parts. We divide these 94 pieces (47 muffins) as evenly as possible among the 124 4-parts. 47 pairs of 4-parts contain both halves of a muffin, which I'll call an A^1 cluster and write
A^1 = [a1*3,m]*2
where m denotes the two muffin halves and the other pieces are denoted a1, indicating a set of pieces of possibly different sizes that occure in A^1 clusters. 34 4-parts contain only muffin pieces whose mates appear in 3-parts. These I call A^0 clusters and write
A^0 = [a0*4]
The 449/258 example uses
30 A^0 clusters ([a0*4])*30 (120 a0 pieces, 30 4-parts) 47 A^1 clusters ([a1*3,m]*2)*47 (282 a1 pieces, 94 4-parts)
Note that the A^1 cluster by itself sets an upper bound on S -- the cluster is 2 persons (size 2r), it cntains 1 complete muffin (size 1, pieces m*2), and it has 6 unmatched muffin pieces (a1*6), giving
S(449/258) <= avg(a1) = (2r-1)/6.
A^0 clusters also bound S by
S(449/258) <= avg(a0) = r/4,
but the A^1 cluster bound is tighter. Note that this (2r-1)/6 bound holds for examples 7/4 and 40/23.
The muffin mates of a0 pieces (resp. a1 pieces) are z0 pieces (resp. z1 pieces). We distribute z0 and z1 pieces as evenly as possible across the 134 3-parts (402 pieces). With 282 z1 pieces, at least 14 3-parts must consist of only z1 pieces. These are Z^0 clusters,
Z^0 = [z1*3] = [z10*3]
where I refine piece labels so that z1 pieces appearing in Z^0 clusters are labelled z10. I create general Z^k clusters by finding minimal sets of persons that contain complete a0/z0 muffins. Maximally even distribution of the 120 z0 pieces places one per 3-part. Then a Z^1 cluster, closed under a0/z0 muffins, is
Z^1 = [a0*4],[z0,z1*2]*4 = A^0,[z0,z11*2]*4
where z1 pieces appearing in Z^1 clusters are relabelled z11.
Z^0 clusters bound S by
S(449/258) <= avg(a10) = 1-avg(z10) = 1-r/3 = (3-r)/3
and Z^1 clusters provide an even tighter bound
S(449/258) <= avg(a11) = 1-avg(z11) = 1-(5r-4)/8 = (12-5r)/8.
The 449/258 example uses
14 Z^0 clusters = ([z10*3])*14 ( 42 z10 pieces, 14 3-parts) 30 Z^1 clusters = (A^0,[z0,z11*2]*4)*30 (240 z11 pieces, 120 3-parts)
As before, we refine the labelling of a1 pieces into a10 and a11 pieces, according to z10 or z11 complements. The next level of clustering is constructed by taking closure under a10/z10 muffins. The 282 a1 pieces in the 47 A^1 clusters are divided into 240 a11 pieces and 42 a10 pieces. Thus at least 5 A^1 clusters must contain only a11 pieces, and with maximally even distribution we have 42 A^1 clusters with 1 a10 piece and 5 a11 pieces. Continuing to refine pieces according to their appearance in A^10 or A^11 clusters, we have
A^10 = A^1 = {a110*6, ...} (6 a110 pieces and some other pieces) A^11 = Z^0, (A^1)*3 = (a111*15, ...)
with 449/258 consisting of
5 A^10 clusters ( 5 A^1 clusters, 30 a110 pieces) 14 A^11 clusters (42 A^1 clusters, 252 a111 pieces)
A^11 clusters provide bound
S(449/258) <= avg(a111) = (7r-6)/15
The 449/258 example lies on the intersection of this bound and the next level cluster bound. The next cluster level takes a110/z110 muffin closure and induces clusters
Z^10 = Z^1 Z^11 = A^10, (Z^1)*6
with 449/258 consisting of
0 Z^10 clusters 5 Z^11 clusters (i.e., only Z^11 clusters)
and bound
S(449/258) <= avg(a1111) = 1-avg(z1111) = (73-32r)/42.
I conclude with some computer generated additional information on these bounds. If anyone sort of understands this post and would like to use my program as is (i.e., no manual and documentation is mostly my posts), drop me a note and I'll send the C++ source (300 lines).
B<4>(r) = (1r-0)/4; S'(r) <= B<4>(r) on (3/2,2/1] tight bound on (3/2,8/5] and at r = (4+8k)/(2+5k) (3/2,8/5] contains mediant(3/2,8/5) = 11/7 S'( (3/2,8/5] ) = (3/8,2/5]; S'(11/7) = 11/28 B<>(r) = (1-0r)/2 B<4>(r) = B<>(r) at r = 2/1 = 2.0000000 S'(2/1) = 1/2 = 0.50000000
B<4,1>(r) = (3-1r)/3; S'(r) <= B<4,1>(r) on [12/7,2/1) tight bound on [9/5,2/1) and at r = (12+9k)/(7+5k) [9/5,2/1) contains mediant(9/5,2/1) = 11/6 S'( [9/5,2/1) ) = [2/5,1/3); S'(11/6) = 7/18 B<4>(r) = (1r-0)/4 B<4,1>(r) = B<4>(r) at r = 12/7 = 1.7142857 S'(12/7) = 3/7 = 0.42857143
B<4,1,1>(r) = (2r-1)/6; S'(r) <= B<4,1,1>(r) on (12/7,7/4] tight bound on (12/7,59/34] and at r = (21+59k)/(12+34k) (12/7,59/34] contains mediant(12/7,7/4) = 19/11 S'( (12/7,59/34] ) = (17/42,7/17]; S'(19/11) = 9/22 B<4,1>(r) = (3-1r)/3 B<4,1,1>(r) = B<4,1>(r) at r = 7/4 = 1.7500000 S'(7/4) = 5/12 = 0.41666667
B<4,1,1,1>(r) = (12-5r)/8; S'(r) <= B<4,1,1,1>(r) on [40/23,7/4) tight bound on [148/85,7/4) and at r = (80+148k)/(46+85k) [148/85,7/4) contains mediant(47/27,7/4) = 54/31 S'( [148/85,7/4) ) = [7/17,13/32); S'(54/31) = 51/124 B<4,1,1>(r) = (2r-1)/6 B<4,1,1,1>(r) = B<4,1,1>(r) at r = 40/23 = 1.7391304 S'(40/23) = 19/46 = 0.41304348
B<4,1,1,1,1>(r) = (7r-6)/15; S'(r) <= B<4,1,1,1,1>(r) on (40/23,228/131] tight bound on (40/23,1119/643] and at r = (228+1119k)/(131+643k) (40/23,1119/643] contains mediant(40/23,47/27) = 87/50 S'( (40/23,1119/643] ) = (142/345,265/643]; S'(87/50) = 103/250 B<4,1,1,1>(r) = (12-5r)/8 B<4,1,1,1,1>(r) = B<4,1,1,1>(r) at r = 228/131 = 1.7404580 S'(228/131) = 54/131 = 0.41221374
B<4,1,1,1,1,1>(r) = (73-32r)/42; S'(r) <= B<4,1,1,1,1,1>(r) on [449/258,228/131) tight bound on [9349/5372,228/131) and at r = (1347+9349k)/(774+5372k) [9349/5372,228/131) contains mediant(134/77,47/27) = 181/104 S'( [9349/5372,228/131) ) = [1107/2686,2267/5502); S'(181/104) = 75/182 B<4,1,1,1,1>(r) = (7r-6)/15 B<4,1,1,1,1,1>(r) = B<4,1,1,1,1>(r) at r = 449/258 = 1.7403101 S'(449/258) = 319/774 = 0.41214470
B<4,1,1,1,1,1,1>(r) = (61r-60)/112; S'(r) <= B<4,1,1,1,1,1,1>(r) on (449/258,764/439] tight bound on (449/258,149516/85913] and at r = (10696+149516k)/(6146+85913k) (449/258,149516/85913] contains mediant(449/258,764/439) = 1213/697 S'( (449/258,149516/85913] ) = (11909/28896,35408/85913]; S'(1213/697) = 32173/78064 B<4,1,1,1,1,1>(r) = (73-32r)/42 B<4,1,1,1,1,1,1>(r) = B<4,1,1,1,1,1>(r) at r = 764/439 = 1.7403189 S'(764/439) = 2533/6146 = 0.41213798
B<4,1,1,1,1,1,1,1>(r) = (1101-487r)/615; S'(r) <= B<4,1,1,1,1,1,1,1>(r) on [160212/92059,764/439) tight bound on [1313469/754729,764/439) and at r = (160212+6567345k)/(92059+3773645k) [1313469/754729,764/439) contains mediant(19549/11233,764/439) = 20313/11672 S'( [1313469/754729,764/439) ) = [1555262/3773645,111271/269985); S'(20313/11672) = 986147/2392760 B<4,1,1,1,1,1,1>(r) = (61r-60)/112 B<4,1,1,1,1,1,1,1>(r) = B<4,1,1,1,1,1,1>(r) at r = 160212/92059 = 1.7403187 S'(160212/92059) = 37941/92059 = 0.41213787
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun