January 2009 - mathfun@mailman.xmission.com

[math-fun] more muffin problem results
by Scott Huddleston 14 Jan '09

14 Jan '09

I found some interesting muffin results and insights by considering a subset of optimal muffin partitions which are "uniform". To simplify terminology and analysis I restrict consideration to muffin instances (m,p) with m muffins >= p people. Solutions for the case m<p then follow by duality, as previously noted. For piece size S(m,p) I normalize muffin size to 1. Conjecture 1: S(m,p) >= 1/3 for all muffin instances with m >= p. I don't have a proof yet, but many cases and the problem structure support this conjecture. Combined with Veit Elser's bound this gives a tight bound S(m,p) = 1/3 for 1 < m/p < 3/2. The basic muffin problem optimizes the maximum size of the minimum muffin piece. Some secondary optimizations: say an optimal partition is "ratio optimal" if it minimizes the ratio of the largest piece to the smallest piece, and "piece optimal" if it minimizes the total number of pieces. Michael Reid's examples have been piece optimal, but ratio optimal partitions provide a nice dimensionless measure of piece sizes. Define R_X(m,p) for a given muffin partition X to be the ratio of the largest piece size to the smallest piece size. Let R_XX(m,p) for a set of partitions XX of (m,p) be the minimum of R_X(m,p) for X in XX. Proposition 2: R_A(m,p) < 2 for every instance (m,p) and A the set of all optimal muffin partitions. Proof: starting from any optimal partition, halve the largest pieces until the proposition holds. Say a muffin partition is "uniform" if |j-k| <= 1 whenever two muffins are split into j and k pieces, respectively, and |a-b| <= 1 whenever two people receive a and b pieces, respectively. Conjecture 3: Every muffin instance has a ratio optimal partition which is uniform; R_U(m,p) = R_A(m,p), where U is the set of uniform optimal partitions. Consideration of uniform partitions gives a handle on bounding piece sizes. Conjecture 4: The number of pieces per muffin in a uniform ratio optimal muffin partition is: a). 1 if m is kp for some k >= 1; b). 3 if m/p = 4/3; b). 2 or 3 if 1 < m/p < 3/2; c). 2 otherwise. For 3/2 < m/p < 2, each muffin is split into 2 pieces and each person receives either 3 or 4 pieces. Persons receiving 3 pieces must have some piece of size at least m/3p, and its complement piece in a muffin has size at most 1-m/3p. The ratio of the pieces is (m/3p)/(1-(m/3p)) = m/(3p-m). This bound appears to be tight over a range of values. Conjecture 5: For 9/5 < m/p < 2, R_U(m,p) = m/(3p-m) and S(m,p) = 1-m/3p. Here are some example partitions m/p. These are given with integral pieces, which one may normalize if desired. I believe these are all optimal. 7/5: pieces 5,7,8: 5.5.5, 7.8*6; 7.7.7*2, 8.8.5*3 S = 1/3, R_U = 8/5 (note: 7.8*6 = 6 muffins split 7.8, 8.8.5*3 = 3 people with pieces 8.8.5) 10/7: pieces 7..13: 7.7.7, 13.8*3, 12.9*3, 11.10*3; 7.11.12*3, 3.9.13*3, 10.10.10 S = 1/3, R_U = 13/7 11/10: pieces 10..19: 10.10.10*2, 11.19*2, 12.18*2, 13.17*2, 14.16*2, 15.15; 10.10.13*2, 10.11.12*2, 14.19*2, 15.18*2, 16.17*2 S = 1/3, R_U = 19/10 12/7: pieces 3..4: 3.4*12; 3.3.3.3*3, 4.4.4*4 S = 3/7, R_U = 4/3 9/5: pieces 4..6: 5.5*3, 4.6*6; 6.6.6*2, 4.4.5.5*3 S = 2/5, R_U = 3/2 16/9: pieces 11.16: 11.16*12, 12.15*2, 13.14*2; 16.16.16*4, 11.11.11.15*2, 11.11.12.14*2, 11.11.13.13 S = 11/27, R_U = 16/11 23/13: pieces 21..31: 21.31*12, 22.30*6, 23.29*4, 26.26; 31.31.30*6, 21.21.21.29*4, 22.22.22.26*2, 23.23.23.23 S = 21/52, R_U = 31/21 7/4: pieces 5..7: 5.7*6, 6.6; 7.7.7*2, 5.5.5.6*2 S = 5/12, R_U = 7/5 17/9: pieces 10..17: 10.17*6, 11.16, 12.15, 13.14*9; 17.17.17*2, 10.12.13.16, 10.13.13.15, 11.13.13.14, 10.13.14.14*4 S = 10/27, R_U = 17/10 Conjecture 6: S(km,kp) = S(m,p) and R_U(km,kp) = R_U(m,p) for k > 1. This could have a simple proof, or very interesting counterexamples.

1 0

Re: [math-fun] Passing thought for a textbook
by Hilarie Orman 13 Jan '09

13 Jan '09

> Just a passing thought: A mathematics textbook with a single > exercise at > the front of the book which reads, > > Every proof in this book has one (deliberately introduced) > technical error, > and may also have inadvertent errors. Correct all proofs. Sounds like a mathematician's version of "A Boy Named Sue". Hilarie

2 2

[math-fun] help needed with D.E.
by N. J. A. Sloane 13 Jan '09

13 Jan '09

I've been struggling with a differential equation in one variable with variable coefficients. Neither Maple nor Mma could solve it, and indeed there may well be no closed form solution. But if there IS I would like to know about it, so I'm asking if anyone here can solve it. Let A(x) = Sum_{n>=0} a(n)*x^n/n! = 1 + 3*x + 31*x^2/2! + 45296*x^3/3! + 4061871*x^4/4! + ... be the exponential generating function for the sequence A144416. This sequence satisfies a complicated recurrence: Define U1:=n->(9/2)*n^2+(63/2)*n+105/2; U2:=n->(9/2)*n^2+24*n+34; U3:=n->6*n+23/2; U4:=n->5/2; then a(n+4)-U1(n)*a(n+3)-U2(n)*a(n+2)-U3(n)*a(n+1)-U4(n)*a(n) = 0 for n >= 0. Let Ai be shorthand for the i-th deriv of A(x) wrt x. Then the recurrence becomes the differential equation: A4 = ((9/2)*x^2*A5+36*x*A4+(105/2)*A3) + ((9/2)*x^2*A4+(57/2)*x*A3+34*A2) + (6*x*A2+(23/2)*A1) + (5/2)*A , with initial conditions A(0)=1, A'(0)=3, A''(0)=31, A'''(0)=842, A''''(0)=45296. It's unlikely, but can this be solved, e.g. in terms of hypergeometric functions? Neil

2 2

Re: [math-fun] muffin problem
by Michael Reid 12 Jan '09

12 Jan '09

> Here are my lower bounds for U(m, n): > > 1 2 3 4 5 6 7 8 9 > 1 1 > 2 1 2 > 3 1 1 3 > 4 1 2 1 4 > 5 1 1 5/4 3/2 5 > 6 1 2 3 2 2 6 > 7 1 1 5/4 5/3 5/3 2 7 > 8 1 2 4/3 4 2 2 9/4 8 > 9 1 1 3 7/4 2 3 5/2 3 9 > > The entry in column 4 row 7 is the bound on U(4, 7), which in fact > equals the > optimum value that was the subject of previous posts ( U(m, n) = m n T > (m, n) ). > I suspect several of my bounds are optimal values. I'm happy to > supply the > partitions to anyone interested. i've also "calculated" some values. recall that my T(m, n) is the maximum c such that there exists a partition of 1 with each part >= c , and which is a simultaneous refinement of 1/m + 1/m + ... + 1/m = 1 and of 1/n + 1/n + ... = 1/n = 1 . i believe i have a valid proof for each of the values below. i also give one such partition for each; showing that it's a refinement is easy. T(m, n) = 1/n if m divides n ; n * 1/n T(2, 2n+1) = 1/(2(2n+1)) ; (4n+2) * 1/(2(2n+1)) T(3, 4) = 1/12 ; 12 * 1/12 T(3, 5) = 1/12 ; 4 * 1/12 + 2 * 1/10 + 4 * 7/60 T(3, 7) = 5/84 ; 4 * 5/84 + 6 * 1/14 + 4 * 1/12 T(3, 8) = 1/18 ; 6 * 1/18 + 6 * 5/72 + 2 * 1/8 T(3, 10) = 2/45 ; 6 * 2/45 + 6 * 1/18 + 2 * 1/10 T(3, 11) = 1/24 ; 8 * 1/24 + 2 * 1/22 + 8 * 13/264 + 2 * 1/11 T(3, 13) = 11/312 ; 8 * 11/312 + 2 * 1/26 + 8 * 1/24 + 4 * 1/13 T(4, 5) = 3/40 ; 4 * 3/40 + 2 * 1/10 + 4 * 1/8 T(4, 6) = 1/12 ; 12 * 1/12 T(4, 7) = 5/84 ; 6 * 5/84 + 2 * 1/14 + 6 * 1/12 T(4, 9) = 7/144 ; 8 * 7/144 + 2 * 1/18 + 8 * 1/16 T(4, 10) = 1/20 ; 20 * 1/20 T(4, 11) = 9/220 ; 10 * 9/220 + 2 * 1/22 + 10 * 1/20 T(4, 4n+2) = 1/(2(4n+2)) ; (8n+4) * 1/(2(4n+2)) T(5, 6) = 1/15 ; 6 * 1/15 + 6 * 1/10 T(5, 7) = 1/21 ; 3 * 1/21 + 6 * 1/15 + 6 * 8/105 T(5, 8) = 1/20 ; 4 * 1/20 + 4 * 3/40 + 4 * 1/8 T(5, 9) = 2/45 ; 6 * 2/45 + 6 * 1/15 + 3 * 1/9 T(6, 7) = 1/21 ; 12 * 1/21 + 6 * 1/14 T(6, 8) = 1/24 ; 24 * 1/24 T(6, 9) = 1/18 ; 18 * 1/18 these appear to agree with your lower bounds on the overlap. mike

1 0

Re: [math-fun] muffin problem
by Michael Reid 12 Jan '09

12 Jan '09

i'll do it in the framework of partitions of 1 . define the mesh of a partition to be its smallest part. rich's partition is 5/84 + 5/84 + 5/84 + 5/84 + 5/84 + 5/84 + 1/14 + 1/14 + 1/12 + 1/12 + 1/12 + 1/12 + 1/12 + 1/12 , which has mesh 5/84 , and is simultaneously a refinement of 1/4 + 1/4 + 1/4 + 1/4 and of 1/7 + 1/7 + 1/7 + 1/7 + 1/7 + 1/7 + 1/7 . if some 1/4 is split into 5 or more parts, then the mesh is <= 1/20 < 5/84 . since 1/4 cannot be a part of 1/7 , each 1/4 must be split into at least 2 parts. suppose some 1/4 is split into exactly 2 parts, say 1/4 = a + b , where a <= b . we have 1/8 <= b <= 1/7 , so 3/28 <= a <= 1/8 . now a occurs as a part of 1/7 , so it has another part at most 1/7 - a <= 1/7 - 3/28 = 1/28 < 5/84 . thus, in an optimal partition, each 1/4 is split into 3 or 4 parts. if some 1/7 is split into 3 or more parts, then the mesh is <= 1/21 < 5/84 . if some 1/7 is not split, then it must occur as a part of some 1/4 . as above, this 1/4 must be split into at least 3 parts, so one of the other parts is at most (1/4 - 1/7) / 2 = 3/56 < 5/84 . thus, in an optimal partition, each 1/7 is split into exactly 2 parts. therefore, there are exactly 14 parts, and 2 of the 1/4 's are split into 3 parts, and the other 2 split into 4 parts. consider a 1/4 that is split into 3 parts. we then have 1/4 = a + b + c , where a <= b <= c , so c >= 1/12 . this occurs as a part of 1/7 , so the other part is 1/7 - c <= 5/84 . this proves that the mesh is at most 5/84 in all cases. moreover, if the mesh is indeed 5/84 , then the 1/4 's that are split into 3 parts must both split as 1/12 + 1/12 + 1/12 . each of these six 1/12 's must be part of 1/7 , which each split as 1/12 + 5/84 . so now there are six parts of 5/84 , and this shows that the two 1/4 's that split into 4 parts must both split as 5/84 + 5/84 + 5/84 + 1/14 . this proves that the partition is the same as rich's. mike

2 1

Re: [math-fun] Passing thought for a textbook
by Dan Asimov 12 Jan '09

12 Jan '09

Fred wrote: << Anyone who has attempted seriously to program mathematical algorithms for computer [an activity almost co-extensive with theorem- proving] will be aware of the pleasurable momentary surge of astonishment when a progam of --- say --- ten lines or so apparently works at the first attempt; not to mention the familiar incredulous frustration when closer investigation establishes that it in practice still fails to do after the tenth. It follows that any proof published at the research level is almost certainly technically incorrect --- even discounting failures at the "typographical" level, which might be dismissed as amenable to an informed reader's error-correction facility. A less obvious consequence involves the observable inherent reluctance on the part of most readers to accept that a purported proof is fallacious, particularly once it has been digested and (unconsciously) accepted. >> Very interesting hypothesis! But I can't agree. Most published math papers I've seen are flawless (proofwise, not exposition-wise). There still remain a significant number of errors, but having done a lot of both theorem-proving and computer programming, I feel it's far easier for a programming error to hang around a long time than a math error. The math error will introduce a contradiction somewhere (even if it leads to a flawed proof of a true theorem), so is ultimately untenable. The programming error may be what I call Type 3: (it compiles, it runs, but it doesn't do what you wanted). Such a program actually exists in the real world, so no contradiction is involved. There may be no way to learn anytime soon whether its output is right or not. There are a few famous cases of math errors hanging around for many years (e.g., Kempe's attack on the 4-color theorem was believed for 11 years; part of Hilbert's 16th Problem problem (Dulac claimed to prove that any planar polynomial vector field has only finitely many limit cycles; a flaw was found 58 years later. (In 1988 it was finally proved.) But the reason these are famous is that they are extremely rare. A published math error, in a field within the mainstream, will usually be spotted fairly soon by experts in the field, especially now that dissemination of papers via the arXiv works so well. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] Passing thought for a textbook
by Steve Witham 11 Jan '09

11 Jan '09

>From: "Fred lunnon" <fred.lunnon(a)gmail.com> > > Anyone who has attempted seriously to program mathematical >algorithms for computer [an activity almost co-extensive with theorem- >proving] will be aware of the pleasurable momentary surge of >astonishment when a progam of --- say --- ten lines or so apparently >works at the first attempt; not to mention the familiar incredulous >frustration when closer investigation establishes that it in practice still >fails to do after the tenth. > >It follows that any proof published at the research level is almost >certainly technically incorrect --- even discounting failures at the >"typographical" level, which might be dismissed as amenable to an >informed reader's error-correction facility. _The Elements of Programming Style_, by Kernighan and Plauger, famously headed its sections with examples of bad style taken from other textbooks. I'm not sure whether it was that book, or maybe one of these: _Software Tools_ by Kernighan, _Structure and Interpretation of Computer Programs_, by Ableson, Sussman and Sussman or ? ...which boasted that every code example was automatically tested by a script that extracted it from the source text as sent to the typesetting software. Looking at SICP, there are a lot of exercises asking you to debug pieces of code. Sussman's PhD thesis was on a program that wrote incorrect programs and tried to fix them. --Steve

2 1

Re: [math-fun] Passing thought for a textbook
by Dan Asimov 11 Jan '09

11 Jan '09

Erich wrote: << those of us that value the moore method (having students prove ALL the results of a course, as well as discover some of them for themselves) know the value in assigning exercises of the form: "prove the following or find a counterexample". assign enough of these, and the student reflexively will know that any "stated truth" is suspect until proven. those of you have not tried the moore method, don't knock it until you try it. you cover far less material, but the students understand it much better because they "own" it. >> My one exposure to the Moore method was very positive. It was in a summer NSF math program just before senior yr. of college -- 1967 -- held at UC Riverside. (110 deg. F. every day in July & August!) The subject was, appropriately enough, point-set topology, and it was totally engaging. The main teacher -- or should I say facilitator? -- was Robert F. Jolly, who'd been nurtured in the "Texas topology" environment. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] Passing thought for a textbook
by Dave Dyer 11 Jan '09

11 Jan '09

I can't help but think that this is a fine way for an expert to hone his skills and amuse himself, but a lousy way for a student to learn the craft.

3 2

Re: [math-fun] Passing thought for a textbook
by Dan Asimov 11 Jan '09

11 Jan '09

<< On Sat, Jan 10, 2009 at 3:52 PM, Fred lunnon <fred.lunnon(a)gmail.com> wrote: > Did you have any particularly (counter-) instructive instances in mind? > [Present company excepted, naturally!] WFL > Actually, no. My main reason for such a textbook would be to encourage students to read through all proofs carefully and skeptically, and not just the ones in the textbook. I envision a book that is still focused on one topic (such as Number Theory), not a textbook on reading proofs, per se. >> Having students read proofs skeptically is of course an important goal, but I don't see the need for such an eccentric textbook in order to accomplish it. (They also need to have model proofs to learn from as well, and I suspect they'd get very annoyed with such an untrustworthy book very soon.) The goal can be accomplished by judicious use of classroom time, HW, & exams. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1