January 2010 - mathfun@mailman.xmission.com

[math-fun] muffin problem -- clusters and bounds
by Huddleston, Scott 01 Dec '17

01 Dec '17

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

2 1

Re: [math-fun] Disk polyominoes
by Allan Wechsler 13 Apr '12

13 Apr '12

A funster who might or might not wish to remain anonymous has corrected me in private. A3 does not equal 2; it equals 1. The corrected sequence is: 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 3, 3 ... As before, I'm not entirely confident of the last couple of values. Thank you for the correction.

5 15

[math-fun] Machine Go
by rcs＠xmission.com 11 Oct '11

11 Oct '11

Science Daily has a report of a recent success for a Go program. http://www.sciencedaily.com/releases/2009/05/090514083931.htm The program Huygens defeated two professional Go players. The program had handicaps of 6 or 7 stones. Question for the Go players among us: Does a handicap of 6 stones mean that the starting board has 6 stones added for the weaker player, or that 6 is added to the final score? Rich

5 5

[math-fun] Isodiametric problem
by victor miller 16 Sep '10

16 Sep '10

A few days ago, at the AMS meeting, I saw a neat talk by Michael Mossinghoff about "isodiametic" problems -- e.g. Fix the diameter of a conv ex n-gon and ask for the ones with maximum perimeter. He reduced the problem to finding univariate polynomials whose non-zero coefficients alternate between +/- 1 and are divisible by a particular cyclotomic polynomial.. He was able to calculate all such up to about 500. Each such polynomial is compactly encoded by th length of the gaps between the non-zero terms. For small n almost all were periodic. He showed how a certain family of periodic constrctions give solutions, but as n got bigger the "sporadic" ones swamped them. He conjectued that these are eventually all of them. He had lots of pictures. The paper is not available yet. Victor

7 9

Re: [math-fun] cybernetics
by Dan Asimov 31 Jan '10

31 Jan '10

Harold writes: << I havent heard the term applied to the internet, and I think it has somewhat fallen out of favor and been forgotten. >> Maybe not cybernetics, but the prefix cyber-, is what I was saying: << I know, or think I know, Norbert Wiener coined the word cybernetics and wrote a book about it. Beyond that, I know the prefix cyber- has often been used to mean computer- or Internet-related. >> E.g., < www.m-w.com > defines cyber- as follows: << : of, relating to, or involving computers or computer networks (as the Internet) <the cyber marketplace> --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

4 3

Re: [math-fun] Riemann integration question
by James Propp 31 Jan '10

31 Jan '10

I asked some other folks via MathOverflow and got an answer; see http://mathoverflow.net/questions/13344/dependence-of-error-on-mesh-for-rie… Jim

1 0

[math-fun] Riemann integration question
by James Propp 30 Jan '10

30 Jan '10

I've got another question arising from the honors calculus course I teach. Suppose f is continuous on [a,b] with I = int_a^b f(x) dx, and for every epsilon > 0 let delta(epsilon) be the largest delta > 0 such that every Riemann sum arising from a partition of [a,b] with mesh less than delta differs from I by less than epsilon. Is it true that (leaving aside the case where f is constant) delta(epsilon) goes to zero like epsilon^2, in the sense that delta(epsilon)/epsilon^2 is bounded above and below by constants as epsilon goes to zero? Jim Propp

3 2

Re: [math-fun] cybernetics
by Dan Asimov 28 Jan '10

28 Jan '10

I know, or think I know, Norbert Wiener coined the word cybernetics and wrote a book about it. Beyond that, I know the prefix cyber- has often been used to mean computer- or Internet-related. But I strongly doubt the organizers of "Cybernetics: Art, Design, Mathematics - A Meta-Disciplinary Conversation" have the vaguest idea of the dictionary definition of cybernetics: << : the science of communication and control theory that is concerned especially with the comparative study of automatic control systems (as the nervous system and brain and mechanical-electrical communication systems) >> Rather, they're just thinking: Let's get a bunch of people in these disparate but somewhat related fields together and see what happens. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

Re: [math-fun] cybernetics
by Dan Asimov 28 Jan '10

28 Jan '10

P.S. I'm fairly suspicious of "cybernetics", because on the one hand it's touted as a rigorous discipline but on the other hand I've never heard of even one theorem (or established fact) in the field. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] cybernetics
by James Propp 28 Jan '10

28 Jan '10

Do any of you know anything about the American Society for Cybernetics? They've announced a conference this summer called "Cybernetics: Art, Design, Mathematics - A Meta-Disciplinary Conversation"; it could be thought-provoking, or it could be flakey. (Or it could be both, I suppose.) See http://www.asc-cybernetics.org/2010/?page_id=3 Jim Propp

2 1