July 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

Re: [math-fun] dumb question about general relativity
by Steve Witham 19 Aug '09

19 Aug '09

It seems to me that if we on the outside of a black hole never see things fall past the event horizon, then a white hole is just a black hole with stuff already rushing out from the event horizon. In other words, nothing can escape from inside a black hole, but then, nothing ever gets that far in anyway. An observer falling into a black hole continues past the event horizon onto a piece of paper that branches off from our history; I don't see why white hole ejecta can't have started on a similar side track-- except that both those tracks seem "non-falsifiable". I guess a singularity is a place where a scientific theory continues majestically past science? What I really want are gray holes, randomly absorbing and ejecting large chunks of matter contrary to all probability but consistent with "classical GR". It's hard to imagine a black hole forming after the big bang and *then* ejecting something. You have to imagine a very red-shifted thing accelerating from +.999...c to -.999...c -- how did it get up the gumption in such a short time? Was it actually in a tight chaotic orbit all along? >From: Rowan Hamilton <rowanham(a)gmail.com> > >Classical mechanics is invariant under translations in time - this >results in conservation of energy via Noether's Theorem. Looking at http://en.wikipedia.org/wiki/Noether%27s_theorem it looks like the only kind of symmetries it applies to are transformations that you can have continuous versions of, like translation and rotation. Is this true? It makes me sad! I would have liked a conservation law to pop out of *every* kind of symmetry! >Classical mechanics is *not* invariant under time reversal, as others >have pointed out, since this violates the >Second Law of Thermodynamics. I second the motion to marginalize the second law to statistics and revert to time-reversible physics. Surely a time-reversed black hole is allowed under a time-reversed Second Law. I'm curious how to tell whether the Second Law is working in forward or reverse. I can take two measurements of entropy, but looking at my log, how do I know whether the 1:01pm measurement was taken before or after the 1:03pm measurement? --Steve

7 12

[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

[math-fun] Double agents, triple agents, and quadruple agents
by Paul Reiners 08 Aug '09

08 Aug '09

I'm not sure whether this is a math/logic question or a psychology question, but it seems to me to be at least partly a math question: I know there have been double agents (for example, Guy Burgess) and I know there have been triple agents (maybe Kim Philby, I read somewhere). Have there been quadruple agents? Would that make sense? If it doesn't make sense, is that be for human psychology reasons alone or for logical reasons, also? (I'm pretty sure there's no logical reason why there couldn't be.)

3 2

[math-fun] factoring almost completely monic polynomials
by Erich Friedman 08 Aug '09

08 Aug '09

for integers m and n, i've been factoring (over the integers) the polynomials: P = (x^n-1) / (x-1) - m obviously when m = (k^n-1)/(k-1) for some integer k, there is a linear factor. i'm interested in the cases when P factors without a linear factor. i've only found 6 cases: (x^8-1)/(x-1) - 3 = (x^3 + x – 1)(x^4 + x^3 + x + 2) (x^14-1)/(x-1) - 4 = (x^3 + x^2 – 1)(x^10 + x^8 + x^7 + 2x^5 + x3 + 2x^2 – x + 3) (x^5-1)/(x-1) + 11 = (x^2 + 3x + 4)(x^2 – 2x + 3) (x^9-1)/(x-1) + 19 = (x^4 – x^3 + x^2 – 3x + 4)(x^4 + 2x^3 + 2x^2 + 4x + 5) (x^11-1)/(x-1) - 23 = (x^2 + x + 2)(x^8 – x^6 + 2x^5 + x^4 – 4x^3 + 3x^2 + 6x – 11) (x^6-1)/(x-1) - 56 = (x^2 – x + 5)(x^3 + 2x^3 – 2x – 11) is there some rhyme or reason for these, or are they just random? erich

4 7

Re: [math-fun] pebbles via computer
by Mark Niemiec 06 Aug '09

06 Aug '09

James Propp<jpropp(a)cs.uml.edu> wrote: > If Conway were still posting to math-fun, he'd probably reply > that I'd be better off just making numbered counters and moving > them around. His early work on the Game of Life was done by > hand, and he's of the opinion that some of the insights he > gained from this couldn't have been gained if he'd just had > a computer do the simulations. Most of my early discoveries in Life were also done by moving counters around on a board. And once personal computers became readily available, most of my subsequent ones have been done by single-stepping patterns to observe the state transitions of single cells (rather than just running things at high speed for hundreds or thousands of generations). Sometimes, it can be useful to try to smash a glider into a pattern in every possible orientation (which is amenable to massive parallelization and iteration techiques), but much more often, problems require great precision. For example, synthesis of an object from gliders often requires a specific cell to be turned on or off at a specific time. This requires careful analysis of the entire history of specific cell and its immediate environment, and often requires complicated Rube-Goldberg style machinations. This requires finesse rather than brute force. David Buckingham, who has probably done most of the work on synthesizing most small objects (both simple and complicated) from gliders, would likely express similar sentiments. Many of his syntheses require making slight adjustments to random mushes that occur dozens or even hundreds of generations after gliders collide - which necessarily require observing such interactions in detail one generation at a time, something easy to do when advancing patterns slowly by hand (using counters or a computer), but which would be totally missed when running patterns at high speed. -- Mark D. Niemiec <mniemiec(a)gmail.com>

3 3

Re: [math-fun] L versus 2L
by rwg＠sdf.lonestar.org 05 Aug '09

05 Aug '09

DanA> Interesting that "pace" means 2 steps. > > It certainly also means just 1 step, in common parlance. > > Just one of those little contradictions of language. > Here is def. 3 for pace, according to < www.m-w.com >: > > 3 a : step 2a(1) b : any of various units of distance based on the length of a human step > > and this is def. 2a(1) for step: > > 2 a (1) : an advance or movement made by raising the foot and bringing it down elsewhere > > --Dan > The off-line (and far superior) MW gives 3 a : a movement of the foot over a space to a new position in walking, running, or dancing : STEP *took a pace or two in the room Guy McCrone* b (1) : the space traversed by one step used as an indefinite unit of measure *cannot go five paces without seeing some wretched object Irish Digest* (2) : any of various units of distance based on the length of a human step at a specified time (as for quick time 30 inches and for double time 36 inches) see ROMAN PACE roman pace: an ancient Roman unit of length that is equal to five Roman feet or 4.85 English feet and is measured in pacing from the heel of one foot to the heel of the same foot when it next touches the ground >From the MW etymology, apparently passuum is genitive. We were taught that "mile" came from millia passus, which gets lots of Google hits in Latin texts, but MW likes milia. --rwg ROMAN PACE CAMPANERO

2 1