March 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] parametrizing the Koch snowflake curve
by Bill Gosper 24 Apr '15

24 Apr '15

Fourier epicycles thru nth: (d16) sum(((product((1 - (( - 1)^j * tan(((%pi * (2 * k + (1/3)))/(2^j)))/(sqrt(3)))),j,1,inf)) * (%e)^(%i * (6 * k + 1) * t)/((2 * k + (1/3))^2)),k, - n,n) See http://www.tweedledum.com/rwg/cog.htm Also http://gosper.org/fst.dvi Pix: http://gosper.org/fst1.png ,http://gosper.org/fst2.png , http://gosper.org/fst3.png ,http://gosper.org/fst4.png . (For parametric, take Re and Im.) Rich's base 4 recursion loops for rational arg. Find the fixed point of the pending stack ops to simulate infinite recursion, and get an exact val on the curve. Equate to this Fourier series for a *non-obvious* identity. --rwg > If you view the starting triangle as running from 0 to 3, > and write the fraction base 4, you can use the > fraction digits to select which part of the (sub)edge > you are on. The orientation of the edge can be calculated > from the 1s and 2s of the high order portion of the fraction, > and that should give a somewhat kludgy sum for the (x,y) > coordinates of the image point. > RWG likely has some nice FFT clock sum expression. > > Rich > > > -----Original Message----- > From: math-fun-bounces(a)mailman.xmission.com [mailto: math-fun-bounces(a)mailman.xmission.com] On > Behalf Of N. J. A. Sloane > Sent: Thursday, February 25, 2010 12:43 PM > To: math-fun(a)mailman.xmission.com > Cc: njas(a)research.att.com > Subject: Re: [math-fun] parametrizing the Koch snowflake curve > > Jim Propp asked: > >> Does anyone (Bill Gosper, maybe?) know an explicit parametrization > of the Koch snowflake curve? > > The Cantor set consists of the points 0 <= x <= 1 which have a base 3 "decimal" expansion that > does not contain a 1. Is there a similar characterization of the Koch snowflake? > > Neil Sloane > >

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

[math-fun] Mixed Doubles correction
by Richard Hess 31 Mar '10

31 Mar '10

Here is a corrected 8-round set of scheduled matches for the mixed doubles problem. Best, Dick Hess Best Known Mixed Doubles Scheduling for 20 Players Court 1 Court 2 Court 3 Court 4 Court 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 10 7 18 3 12 19 4 5 8 13 2 9 16 17 6 11 20 15 14 1 16 19 2 3 6 17 10 5 18 15 12 7 20 11 8 9 14 13 4 1 4 15 6 3 14 5 12 7 16 9 20 11 10 17 2 13 8 19 18 1 20 5 10 3 8 11 16 7 12 15 2 9 6 19 14 13 18 17 4 1 14 17 8 3 2 15 18 5 20 9 4 7 10 19 16 11 6 13 12 1 12 13 20 3 18 7 14 5 4 17 16 9 8 15 10 11 2 19 6 1 8 9 12 3 20 13 6 5 16 11 18 7 2 17 14 15 4 19 10

1 0

[math-fun] Mixed Doubles Scheduling
by Richard Hess 30 Mar '10

30 Mar '10

Dear Funsters, Progress on an outstanding Mixed doubles scheduling problem was made at the recent Gathering for Gardner (G4G9). The problem is to schedule 20 mixed doubles participants in as many rounds as possible, with all players participating in each round but never playing with the same partner or facing the same opponent twice. A player is permitted to play with and against the same player in different rounds. An upper bound is 9 rounds as there are only 9 same sex opponents available. As reported in A lifetime of Puzzles (Demaine, Demaine, Rodgers) (2008), the best solution known was 7 rounds. At G4G9 I had the luck to sit next to Josh Purinton (josh(a)purinton.org) and gave him the problem. In less than 24 hours he had sent it to a solving algorithm and produced the table below. This still leaves open the question if the maximum of 9 rounds is possible. Also an open problem is whether 9 rounds is possible for men's or women's doubles. I invite funsters to cogitate and comment. Happy puzzling, Dick Hess Best Known Mixed Doubles Scheduling for 20 Players Court 1 Court 2 Court 3 Court 4 Court 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 10 17 18 3 12 19 4 5 8 13 2 9 16 17 6 11 20 15 19 1 16 19 2 3 6 17 10 5 18 15 12 7 20 11 8 9 14 13 4 1 4 15 6 3 14 5 12 7 16 9 20 11 10 17 2 13 8 19 18 1 20 5 10 3 8 11 16 7 12 15 2 9 6 19 14 13 18 17 4 1 14 17 8 3 2 15 18 5 20 9 4 7 10 19 16 11 6 13 12 1 12 13 20 8 18 7 14 5 4 17 16 9 8 15 10 11 2 19 6 1 8 9 12 3 20 13 6 5 16 4 18 7 2 17 14 15 4 19 10

1 0

[math-fun] Penrose Tilings - Grunbaum-Shephard Theorem 10.6.1
by rcs＠xmission.com 30 Mar '10

30 Mar '10

Date: Thu, 25 Mar 2010 10:32:33 -0700 Subject: Penrose Tilings - Grunbaum-Shephard Theorem 10.6.1 From: Noah Davidson <davidson(a)reed.edu> I am studying Penrose tilings and Ammann bars for my undergraduate thesis. After some thought, the proof of Grunbaum-Shephard Theorem 10.6.1 is giving me trouble. If someone on this list has thought carefully through the argument and is willing to discuss it with me briefly off list, I would be grateful. Thanks you kindly, Noah Davidson

1 0

[math-fun] A cautionary tale of 6 polynomials in 10 variables
by Fred lunnon 29 Mar '10

29 Mar '10

A cautionary tale of 6 polynomials in 10 variables _______________________________________ Some relevant, useful, or just pretty facts concerning Sp(2n) --- (0) Given n, all nonsingular real skew-symmetric 2n x 2n matrices are equivalent; so fix on the convenient canonical choice K == [[O_n, -I_n], [I_n, O_n]], where O_n, I_n denote n x n zero, unit matrices resp. (1) The "symplectic group" Sp(2n) comprises real 2n x 2n matrices M such that M' K M = K, where M' denotes transpose of M. (2) For M in Sp(2n), the determinant |M| = +1 always, -1 never; (3) Sp(2n) is generated by products of at most 4n "transvections" I + t U' U K, where U ranges over real nonzero 2n-vectors |R^(2n), t over reals |R. (4) The dimension of Sp(2n) equals (2n+1)_C_2 = (2n+1)n; (5) If M = Q S denote the polar decomposition of symplectic M into a unique product of orthogonal Q matrix and symmetric matrix S, then Q,S must also be symplectic; (6) Sp(2n) is a connected Lie group, though not compact; (7) PSp(2n), its "projective symplectic" quotient with scalars factored out, is simple; (8) Mp(2n), its "metaplectic" double cover, is simply connected. (9) Mp(2n) has no (faithful, finite order) matrix representation. I became diverted from an earlier investigation by the unexpected and rather pretty result (6). This familiar situation was doubtless exacerbated by (6) being just about the only item in section 1 of Eckhard Meinrenken's "Symplectic Geometry" (free download online) that I could grasp at sight, and by its proof appearing simple and elegant but quite incomprehensible --- what do diffeomorphisms have to do with a theorem in elementary matrix algebra? So I sat down to investigate (6) by myself. And the first question that occurred to me was: what are the dimensions of the orthogonal and symmetric factors in the polar decomposition of a symplectic matrix? Now physicists by and large don't seem to be terribly interested in Lie groups as such: they are often perfectly content with the Lie algebra --- the vector-space tangent to the identity transformation --- the dimension of which must equal that of the group manifold. Standard results in the literature assert that (10) Lie algebra of Sp(2n) comprises T with T' K + K T = 0; so T = [[A, B], [C, -A']] with B,C symmetric, dimension = 2 (n+1)_C_2 + n^2 = (2n+1)_C_2 = 2 n^2 + n; and (11) Lie algebra of O(2n) comprises T with T' I + I T = 0; so T skew-symmetric; dimension = (2n)_C_2 = 2 n^2 - n; hence (12) Lie algebra of orthogonal symplectic SpO(2n) comprises T = [[A, -B][B, A]], B symm, A skew-symm; dimension = (n+1)_C_2 + n_C_2 = n^2; and (13) By taking the complement of vector space (12) in (11), symmetric symplectic matrices have dimension = 2 n^2 + n - n^2 = n^2 + n = (n+1)_C_2. Much as I mistrust all this high-falutin' abstraction, I'm beginning to wonder if they have a point --- though it should be said in my defence that symmetric matrices, not being a group, are less than amenable to the method. So, just as as a check, I pressed on to try to verify (13) directly. Studiously avoiding an earlier misfortune [involving much earnest investigation of the case n = 1, prior to eventual realisation that actually Sp(2) = SL(2)], I started off with n = 2, for which (13) predicts dimension 6. Setting M = [[z,a,b,d], [a,y,c,e], [b,c,x,f], [d,e,f,w]] and evaluating M' K M = K yields 6 constraints, all of which must vanish: P_1 = b^2 + c*d - f*a - x*z + 1, P_2 = e^2 + c*d - f*a - w*y + 1, P_3 = b*c + e*c - a*x - f*y, P_4 = b*d + e*d - a*w - f*z, P_5 = b*f - e*f + c*w - d*x, P_6 = b*a - e*a - c*z + d*y. It's easy to see informally that these are functionally independent: for each P1,...P6 in turn, set to zero all but b; e; f,y; f,z; d,x; d,y respectively, to yield an expression varying while the other 5 vanish. Or more formally, verify that the 6 x 10 differential matrix [d P_j / d V_i] of linear polynomials in the variables V = [a,b,c,d,e,f,z,y,x,w] has full rank 6. Hence the manifold should have dimension 10-6 = 4; and more generally, dimension = (2n+1)_C_2 - 4 n_C_2 = 2n (?) Comparison with (13) now reveals to the astute observer a trifling discrepancy --- a shortfall of 6-4 = 2 in my bull-at-the-gate estimate for the symmetric symplectic dimension when n = 2; and more generally, of (n+1)n - 2n = (n-1)n = n_C_2. No prizes for guessing which argument is shambolically addled. But just exactly at what point did its misguided author's powers of ratiocination desert him this time round? Fred Lunnon

1 1

[math-fun] A new factor of the Fermat number F12
by Warut Roonguthai 27 Mar '10

27 Mar '10

A 54-digit prime factor of F12 has just been found with GIMPS' ECM. It's the sixth known prime factor of F12. The 1133-digit cofactor is composite. So F12 is still the smallest Fermat number that we cannot factor completely. See http://mersenneforum.org/showthread.php?t=13215 The discovery happened only a day after a factor of F22 was found (also with GIMPS' ECM) and 24 years after Robert Baillie found the fifth known factor by Pollard's p-1 method. Warut

1 1