June 2009 - 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 12 Oct '11

12 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] Now they tell me: Mathematica for $295
by Robert Baillie 15 Aug '09

15 Aug '09

I wish I had known about this before I shelled out big bucks. But maybe others can benefit from this. For $295, you can get a full-featured 32-bit version of Mathematica for use at home. Commercial uses are prohibited. So is using it for the class you teach at a school. But for true math nerds, like me, who consider Mathematica to be recreational software that we use at home, this sounds like a great bargain! http://www.wolfram.com/products/mathematicahomeedition/

4 3

Re: [math-fun] Fractal puzzles
by rwg＠sdf.lonestar.org 11 Jul '09

11 Jul '09

> Thanks, Alan. > > So, does this make it the same as starting with a plus sign of 5 adjacent squares, > and taking 5 congruent copies snuggled together and normalized -- then iterate to > the limit? (Actually the boundary of this limit.) If you do it right, you can start with a square for Q[0] and get the "+" sign for Q[1]. See http://gosper.org/erezd.PNG . These aren't quite the same but they have the same closure and boundary dimension. A toy analogy is the approximations to the unit interval you get by varying Q[0] in the iteration Q[n+1] = (Q[n] U (1+Q[n]))/2. Allan's method, Q[0] := {0}, produces the dyadic rationals. But Q[0] := (0,1] gives the complement of the dyadic rationals. Same closure, utterly unequal measures. You can't zoom down to a self contact because of self similarity. For greater rigor, you can construct sausage links that will remain demonstrably disjoint. You can also write a function analogous to that obscure Peano Mathematica function that will exactly and continuously map the rationals in the unit interval onto one quarter of the boundary in question. There are also open and closed loop spacefills of this region, which can also be computed exactly for rationals. I like D=log_5(9) . Any takers on 3D revisitation? --rwg > If so, it's a fractal I was studying just a couple of months ago. > I'll go review what I had about it. > > =-Dan > > << > I'm pretty sure I understand the intended construction. We'll construct a sequence of sets of > complex numbers; the limit of this sequence will be (well-defined and) the intended fractal. > > Let Q[0] contain only 0. Then for any nonnegative integer i, let Q[i+1] = (Q[i] + {0, 1, -1, > i, -i}) / (2i + 1). Here, if A and B are sets, the set A+B is intended to mean {a+b | a in A > and b in B}. > > Each Q is roughly cross-shaped; RWG observes (very tersely) that dividing by 2i+1 rotates and > shrinks each such cross by just enough that five crosses can snuggle together to make a > meta-cross. > > I think this fractal is in Mandelbrot; I cannot dig up my copy at the moment. >>> > > _____________________________________________________________________ > "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

3 11

[math-fun] Game of Life News
by Ray Tayek 29 Jun '09

29 Jun '09

http://pentadecathlon.com/lifeNews/index.php 2009-May-31 Glider Constructions Glider Construction of Period 177 Oscillator <http://pentadecathlon.com/lifeNews/2009/05/24Gto104P177-2009-05-30.rle?text> 104P177 from 24 Gliders Here's a construction of a Period 177 Oscillator found by Jason Summers. It takes 8 sets of 3 Glider collisions to produce the oscillator engines. (One of the sets of three is shown in blue in the image.) ... --- vice-chair http://ocjug.org/

1 0

[math-fun] Science: IBM Claims Breakthrough In Analysis of Encrypted Data
by Ray Tayek 25 Jun '09

25 Jun '09

http://science.slashdot.org/story/09/06/25/1736230/IBM-Claims-Breakthrough-… An anonymous reader writes "An IBM researcher has solved a thorny mathematical problem that has confounded scientists since the invention of public-key encryption several decades ago. The breakthrough, called 'privacy homomorphism,' or 'fully homomorphic encryption,' <http://www.net-security.org/secworld.php?id=7690>makes possible the deep and unlimited analysis of encrypted information data that has been intentionally scrambled without sacrificing confidentiality." Reader <http://www.elasticvapor.com/>ElasticVapor writes that the solution IBM claims "might better enable a cloud computing vendor to perform computations on clients' data at their request, such as analyzing sales patterns, without exposing the original data. Other potential applications include enabling filters to identify spam, even in encrypted email, or protecting information contained in electronic medical records." ... --- vice-chair http://ocjug.org/

1 0

Re: [math-fun] Integer Sequence True or False?
by James Propp 25 Jun '09

25 Jun '09

Bill Gosper wrote: >If a sequence of integers is periodic modulo every positive >integer, then it obeys a linear or bilinear recurrence with constant >coefficients. E.g., if s(n):= somos4(n)^2, then > > - 4 s(n - 6) s(n - 1) + 29 s(n - 5) s(n - 2) + 116 s(n - 4) s(n - 3) >s(n) = -------------------------------------------------------------------- > s(n - 7) So I posted the following question to the Robbins forum (see the text-file jamespropp.org/about-robbins for a description of the forum, and send me an email if you want to join): ------------------------------------------------------------------------- Bill Gosper asks whether the following extremely general proposition is true or false: If a sequence of integers is periodic modulo every positive integer, then it obeys a linear or bilinear recurrence with constant >coefficients. He follows this by a very specific example: E.g., if s(n):= somos4(n)^2, then - 4 s(n - 6) s(n - 1) + 29 s(n - 5) s(n - 2) + 116 s(n - 4) s(n - 3) s(n) = -------------------------------------------------------------------- s(n - 7) Can we answer Gosper's question in the affirmative for arbitrary powers of somos4? Jim Propp ------------------------------------------------------------------------- Here are the replies I got: >From Ira Gessel: ------------------------------------------------------------------------- [re the general assertion] It's very unlikely to be true in general. For example, the Bell numbers are periodic modulo every positive integer. I'm not sure how to prove that they (or any sequence) don't satisfy a bilinear recurrence with constant coefficients but I'd be very surprised if they do. ------------------------------------------------------------------------- >From Noam Elkies: ------------------------------------------------------------------------- [re the general assertion] I don't think this can be true, because the hypothesis holds if the sequence satisfies *any* reversible polynomial recurrence, including some that grow much too fast to hope for (bi)linearity, e.g. a(n) = a(n-2) + a(n-1)^2009 ... [re the case of powers of somos4] Yes, or even generalized somos-n for n=4,5,6,7. More generally yet, the termwise product of two theta sequences (and thus by induction of any number of theta sequences) is a theta sequence. ------------------------------------------------------------------------- >From Michael Larsen: ------------------------------------------------------------------------- [following up on Noam's first remark] Besides, the set of integer sequences which is periodic modulo every positive integer has the cardinality of the continuum. ------------------------------------------------------------------------- (Note that this is exactly the point that Rich Schroeppel made in math-fun on May 14.) >From Fred Lunnon: ------------------------------------------------------------------------- [following up on Ira's posting] Nice example! And deBruijn's formula gives an asymptotic expression for Bell numbers (essentially just an approximaion to the largest term of the Dobinski sum). So they might do the trick, if we knew a general asymptotic form for the solution of a bilinear recurrence, analogous to polynomial(n)*exponential(n) for a linear recurrence. Something involving exp(n^2), perhaps ... ------------------------------------------------------------------------- >From Richard Stanley: ------------------------------------------------------------------------- It is easy to find a nonrecursive sequence that is periodic modulo every n. Simply define f(0), f(1), f(-1), f(2), f(-2), etc., in turn, using the Chinese remainder theorem to keep the sequence periodic modulo every prime power. There are infinitely many choices at each step, so most of the time we will obtain a nonrecursive sequence. ------------------------------------------------------------------------- Jim Propp

1 0

[math-fun] credit card numbers
by James Propp 25 Jun '09

25 Jun '09

I learned (through entirely licit means) that a friend of mine who lives not far from me has the same first eight digits on her Visa card as mine. (She's probably the only person whose credit card number I know, other than myself and my wife.) How unlikely is this? Does anyone know much about the schemes used in devising credit card numbers? I know that there is at least one check- digit, so the naive estimate 1/10^8 needs to be replaced by 1/10^7 or 1/10^6. Is there any region-coding involved? That would further raise the probability. Jim Propp

9 8