Skip to content

Muffins and Integers

June 21, 2018


A novel cake-cutting puzzle reveals curiosities about numbers

Alan Frank introduced the “Muffins Problem” nine years ago. Erich Friedman and Veit Elser found some early general results. Now Bill Gasarch along with John Dickerson of the University of Maryland have led a team of undergraduates and high-schoolers (Guangqi Cui, Naveen Durvasula, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak, and Sung Hyun Yoo) in writing two new papers that develop a full theory.

Today we discuss the problem and how it plays a new game with integers.

The puzzle was popularized five years ago in the New York Times Online. That spoke of cupcakes not muffins, but Frank’s original term from 2009 has stuck to the pan since muffins are bigger and firmer hence easier to cut. The original question was:

How can one divide {m = 3} muffins among {s = 5} students while maximizing the size {f(m,s)} of the smallest piece?

Everyone will get {3/5} of a muffin. If we cut a {3/5} piece out of the first muffin and give someone else the {2/5} piece left over then that person will also have a piece of size at most {1/5}. That’s no better than the trivial solution of cutting each muffin into fifths. Can we do better?

A Kinder Cut

In fact, we can. Quarter the first muffin—that at least is easy with a knife. With more care we divide the other two muffins into pieces of size {7/20}, {7/20}, and {6/20 = 3/10}. Four people get a quarter and a {7/20} piece giving {(5+7)/20 = 3/5}. The fifth student gets the two {3/10} pieces. So {f(3,5) \geq 1/4}.

Is this optimal? If we divide any muffin into {4} or more pieces, some piece must have size at most {1/4}. On the other hand, if we divide each muffin into at most {3} pieces, we have at most {9} pieces total, so some student gets just {1} piece. That must be a {3/5} piece, leaving a {2/5} piece which implies the need for an at-most {1/5} piece either from halving it or from supplementing it. So we have proved {f(3,5) = 1/4}.

Other cake-cutting problems involve protocols for “fair division” where one person cuts and another chooses. Here the division is constrained to be fair. The depth comes from the problem’s minimax—or maximin—nature. It is not a simple linear programming problem. It is not a two-player game but has game-like aspects. It does have an important duality property.

Duality

The flipped problem is to divide {5} muffins among {3} students. The trivial solution guarantees {f(5,3) \geq 1/3}. We must have at least {10} pieces so some student will get {4} pieces, at least one of size no more than {5/(3*4) = 5/12}. We can achieve that by breaking four muffins into pieces of size {5/12} and {7/12} and the other in half. The other two students each get a {6/12} piece and two {7/12} pieces. This is a full proof of {f(5,3) = 5/12}.

The dual nature of this argument may not be apparent at first but Friedman proved:

Theorem 1 For all {m,s \in \mathbb{N^+}}, {f(s,m) = \frac{s}{m}f(m,s)}.

Proof: Picture Sweeney Todd luring the {s} students into his barbershop with {m} muffins each proffered by a customer of Mrs. Lovett’s Meat Pies. So we have {m} hungry muffin providers who will be served pieces of student pie. If a muffin was shared among {k} students then its owner will get {k} pieces of pie in return. The piece-maximization objective is the same as when the students ate the muffins. The only change is that the piece size is reckoned in proportion to the students rather than the muffins, hence the conversion factor {\frac{s}{m}}. \Box

The paper shows something more: how to convert a proof of optimality of a division in the primal to a proof for the corresponding division in the dual. Above we not only have {f(5,3) = \frac{5}{3}\cdot \frac{1}{4} = \frac{5}{12}} but also the fifth student with the two {3/10} pieces corresponds to the muffin divided into halves, the others with a {1/4 = 5/20} and {7/20} piece showing the {5:7} division out of {\frac{3}{5}\cdot 20 = 12}.

To illustrate another case, {f(8,5)} strikes me as easier to reason about than {f(5,8)}: Splitting each of {8} muffins {\frac{2}{5}:\frac{3}{5}} and giving one student four {\frac{2}{5}} pieces, the others two {\frac{3}{5}} and a {\frac{2}{5}}, achieves {2/5}. Conversely, each student gets an {8/5} total share, so if someone gets a whole muffin then the remaining {3/5} share causes a {\frac{2}{5}} piece somewhere. If not, then there are {16} total muffin pieces, so someone gets four pieces, and the smallest of those has size at most {\frac{2}{5}}. So {f(8,5) = 2/5} and hence {f(5,8) = 1/4}.

One aspect of duality that seems missing, however, is the correspondence between a feasible solution on one side and a constraint on the other. For linear programming this placed it into {\mathsf{NP \cap co}\text{-}\mathsf{NP}} long before Leonid Khachiyan placed it into {\mathsf{P}}. As was shown by Elser, the muffin problem yields a mixed linear and integer program. This is enough to show that {f(m,s)} is computable and always a rational number {q/r} but so far not to place problems about {q} and {r} into {\mathsf{NP}} let alone {\mathsf{P}}. Trying {f(11,5)} instead will show the issues.

Discovering, Charting, and Theory-Building

The duality allows us to limit attention to {m \geq s}. Since cases where {s} divides {m} are trivial, we have {m \geq s+1} and {m/s} not an integer. Then any solution achieving optimal minimum piece size {k = f(m,s)} must satisfy:

  • Every student gets a share of at least two muffins.

  • Every muffin is cut into at least two pieces.

The latter implies {f(m,s) \leq 1/2}. Note that if {s} divides {2m} then we get {f(m,s) = 1/2} by halving each muffin, and vice-versa. So we also consider this a trivial case.

Not so easy to prove, apparently, is {f(m,s) \geq 1/3} (given {m \geq s}). It appears as “Appendix E” of the group’s second paper. That and Bill’s talk slides for the 2018 Joint AMS-MAA Meeting have some updates over the ArXiv paper, even though the latter stretches to 199 pages.

Why is the paper so long? There are 103 pages of appendices and tables. These supplement an original effort to build a theory. It starts by defining {\ell = \lfloor 2m/s \rfloor}, so that nontrivial cases have {\ell < \frac{2m}{s} < \ell+1}, and giving the following basic upper bounds:

Theorem 2 For {m \geq s}, {f(m,s)} is at most the minimum of {\frac{m}{s(\ell+1)}} and {1 - \frac{m}{s\ell}} .

Proof: In an optimal solution, every muffin must be cut into exactly two pieces, else we have {f(m,s) \leq 1/3}. It follows that some students get shares from {(\ell+1)} muffins and others partake in only {\ell} muffins. The former receive some piece of size at most their {\frac{m}{s}} total divided by {(\ell+1)}, hence the first inequality. The latter similarly receive some piece of size at least {\frac{m}{s\ell}}, but then the other piece of the muffin it came from has size at most {1 - \frac{m}{s\ell}}. \Box

The ‘FC’ bounds are tight for {f(8,5) = 8/20 = 2/5}, {f(13,8) = 13/32}, {f(21,13) = 21/52}, and {f(34,21) = 34/84 = 17/42}, so one might expect it to continue for the whole Fibonacci sequence. But it fails for {f(55,34)}: instead of {55/136 = 0.4044...}, this note posted by Bill using methods found by Metz gives an upper bound of {151/374 = 0.4037...} Efforts to bound other progressions lead to theorems like this one:

Theorem 3 If {\frac{5d}{13} \leq a \leq \frac{13d}{29}} and {a \neq \frac{2}{5}d} then putting {X = \max\{\frac{5a-d}{6}, \frac{a+d}{8}, \frac{3a}{7}\}} gives

\displaystyle  f(3dk + a + d, 3dk + a) \leq \frac{dk+X}{3dk+a}.

They have been continually charting more individual solutions and also finding more arguments by which to generate upper and lower bound theorem cases. The efforts have been joined by other students. As we go to post the following bounds—ordered by {s} and stated with common denominators—have yet to be closed:

\displaystyle  \begin{array}{ccccc} 2009/4410 &\leq &f(67,21) &\leq &2010/4410\\ 669/1500 &\leq &f(67,25) &\leq &670/1500\\ ? &\leq &f(61,27) &\leq &281/648\\ 620/1440 &\leq &f(69,32) &\leq &621/1440\\ 273/666 &\leq &f(62,37) &\leq &274/666\\ 591/1440 &\leq &f(67,40) &\leq &592/1440\\ 325/820 &\leq &f(70,41) &\leq &328/820\\ 139/344 &\leq &f(70,43) &\leq &140/344\\ 912/2632 &\leq &f(61,47) &\leq &917/2632\\ 152/441 &\leq &f(64,49) &\leq &153/441\\ 355/1000 &\leq &f(63,50) &\leq &356/1000\\ 209/612 &\leq &f(67,51) &\leq &210/612\\ 110/318 &\leq &f(69,53) &\leq &111/318\\ 552/1540 &\leq &f(67,55) &\leq &553/1540 \end{array}

The `?’ marks a computer run that timed out. The Muffin Team may soon solve some of these, but there are always more to do—unless and until a full characterization is found. This all shows scope for involvement by amateur mathematicians both for finding more-effective duality arguments and for computational experiments.

Higher-Level Questions and Subtleties

The following questions spring to mind—with {m \geq s} and the same nontriviality assumptions as above:

  1. If {f(m,s) = q/r} in lowest terms, then is {r} always a multiple of {s}?

  2. Is there always an optimal solution in which some student gets all equal-size pieces?

  3. If {\gcd(m,s) = a} then does {f(m,s) = f(\frac{m}{a},\frac{s}{a})}—i.e., do things reduce to {a} identical sub-problems?

  4. Is {q/r} given by a simple function of {m/s}—or {q} and {r} by simple integer functions of {m} and {s}?

A mark of subtlety is that the first two answers are no while the other two remain open problems despite all the work. The first holds whenever either bound in Theorem 2 is tight, or when {f(m,s)} equals an alternative bound called {\mathrm{INT}(m,s)} in the long paper. It fails, however, for {f(31,14) = 3/7}. Although it and other known exceptions have {\gcd(r,s) > 1}, even that hasn’t been proved.

My thought with question 2 had been to force some relation between {r} and {s\ell}. But Metz refuted it by showing that {f(35,13) = 64/143} and that no solution gives someone shares of equal size. Here {\ell = \lfloor 70/13\rfloor = 5} but {143 = 11\cdot 13} is not a multiple of {65}. I have posted his note here with their permission.

If an FC or INT bound is tight for {f(m,s)} then it is tight for {f(am,as)} for all integers {a \geq 1}. These bounds are defined in terms of {\frac{m}{s}} alone and are polynomial-time computable. The team have formalized several other bounds with the same or similar properties. But next we discuss a sense in which the original FC bounds are the ultimate answers.

Touches of Hilbert?

For any ideal {I} generated by homogeneous polynomials of some degree {d_0} in variables {x_1,\dots,x_n} over some field {K}, we can set {h_M(d)} to be the dimension of the quotient space {M_d} of homogeneous polynomials of degree {d \geq d_0} modulo the ideal {I}. David Hilbert proved that there is always a polynomial {p_M} such that {h_M(d) = p_M(d)} for all but finitely many {d}. Well, the minimum integer {D_0} such that {h_M(d) = p_M(d)} holds for all {d \geq D_0} may be huge in terms of {d_0} and {n}, but Hilbert first proved it exists and later gave bounds which have since been refined. It is called the Hilbert regularity. The Muffin crew have proved a theorem that strikes me as somehow analogous:

Theorem 4 For all {s > 0} there exists {M_s > 0} such that for all {m \geq M_s}, {f(m,s)} equals one of the bounds in Theorem 2.

They also give a bound of roughly {s^3} on {M_s}. For {s \leq 7} they have computed {M_s} exactly. One consequence of the regularity is that computing {f(m,s)}, while not known to be in {\mathsf{P}} or even in {\mathsf{NP}} in any sense, belongs to the class {\mathsf{FPT}} of fixed-parameter tractable problems.

Their last main topic also bridges between Hilbert’s famous “Program” of automating mathematical deduction—the one supposedly destroyed by Kurt Gödel—and PolyMath projects. They have created a “Muffin Theorem Generator” for exceptional cases, and it is the subject of their second paper. They document its use to solve a sizable initial segment of exceptional cases having {s > 7}, and they have now resolved all for {s} up through {9}.

Open Problems

The high-level problem is to find a criterion that expresses the solution {q/r} as a simple direct function of {m} and {s}. Or might there be irreducible complexity “underneath” the regularity bound {M_s} as {s} varies?

Short of a full characterization, what divisibility properties of integers are being used, in particular regarding {r} and {s}? Their “Muffin Theorem Generator” also gives food for thought on computational experiments—and student research initiatives. Kudos to the students—note the newer bounds in the talk slides in particular.

Advertisements
8 Comments leave one →
  1. June 21, 2018 10:36 pm

    BTW, there is some rationale behind the jumble of {\frac{q}{r}} and {q/r} and {q:r} style ratios: The first is just for the rational value while the second intends to emphasize {q} and {r} individually.

    Here is another worked-out example from an earlier draft of the post:

    “Both the FC and INT bounds are expressible as functions of {m/s} alone. Hence if either is tight for {f(m,s)} then it is tight for {f(Am,As)} for all integers {A}. However, {m = 24}, {s = 11} is a case where neither bound is tight. We have {\ell = \lfloor 48/11\rfloor = 4}, so we get upper bounds of {24/55} and {1 - 24/44 = 5/11}. The latter is redundant but {24/55} is not tight: the true answer is {19/44}.

    We can achieve {19/44} by noting that {s/m = 24/11 = 96/44} and enumerating ways to partition {96} into pieces no smaller than {19} and no bigger than {25}. A five-way partition must be {19+19+19+19+20} while four-way partitions can be {24+24+24+24} or {23+24+24+25} or {23+23+25+25} or {21+25+25+25}. We have 48 total pieces so we need four five-way partitions, so we need 16 muffins to be cut {19:25} and 4 cut {20:24}. To use up sixteen {25} pieces we need 4 students to receive {21+25+25+25} and 2 to receive {23+23+25+25}, so we cut the other 4 muffins {21:23}. Recalling the 4 students with five pieces we have just 1 student left over who gets the {24+24+24+24}. We’ve not only shown an optimal solution but also proved it must give some student all equal-sized pieces.

    The fact of needing four 5-way partitions and seven 4-way partitions does not depend on the denominator being {44} but on the fact of having {48} total pieces to give to {11} students. If the minimum size is to be {19 + \epsilon} then the remainders of the 20 muffins involved in the 5-way partitions will be pieces of size at most {25-\epsilon}. Of the seven students getting a 4-way partition, at least four must get three of size at most {25 - \epsilon}, which must be paired with four pieces of size at least {21+\epsilon'} from the other 4 of the 24 muffins. Those last 4 muffins in turn have other pieces of size at most {23 - \epsilon'}. The finisher is that we cannot make a 4-way partition from muffins of size {25-\epsilon} and {23-\epsilon'}. Hence {19/44} is optimal.

    This treatment of the latter argument is rough but the Muffin Team make it more formal and define a new kind of bound from it…”

  2. June 23, 2018 7:19 pm

    Nice work! This takes me about 4 years, to when I spent somewhere between a summer and a year thinking about this problem obsessively in my spare time. I filled out tables of values of f (actually, I defined theta(m,n) = n f(m,n), because I wanted theta(m,n) = theta(n,m)), but I never found a good algorithm to compute the values. It sounds like you do have good algorithms in many cases, and much larger tables.

    I found a write-up where I gave a proof that (i) f(m,n) is rational, and (ii) “if f(m,n) = p/q, then there exists a procedure to assign the muffins to students where each piece’s size is rational with denominator q.” I assume fact (ii) is known to you? Thanks for reading, I probably would have loved to be a part of your group.

  3. June 23, 2018 7:29 pm

    A more basic question: where f(m,n) = p/q, is there a known integer expression which q must divide? This, together with fact (ii) from my previous comment, would give a simple algorithm to calculate f (though probably not so efficient).

  4. PrincetonPete permalink
    June 24, 2018 11:33 am

    Half each muffin. Give each student a half. Discard the remaining half. Now the min any student gets is 1/2.

  5. Richard Chatwin permalink
    August 22, 2018 2:28 pm

    Just took a quick look at the first four unclosed bounds mentioned above. (67, 21), (67,25),(69, 32) are all similar cases and your lower bound applies in each case. (61, 27) is slightly more complicated but works out nicely: your upper bound applies. A couple of difficult cases are (181, 104) and (1079, 621)!

    • Richard Chatwin permalink
      August 31, 2018 5:58 pm

      Actually, those other two cases aren’t so hard! f(181, 104) = 75 / 182 and f(1079, 162) = 3413 / 8280.

  6. Bill Gasarch permalink
    September 22, 2018 12:19 am

    Actually, over the summer we solved all the cases above.
    1) We have, for every 1\le s \le 60, s \le m \le 70, f(m,s)

    2) We have 3 methods for lower bounds on f(m,s) (which are preocedures) and
    3 for upper bounds. This is of course in hindsight- we used to have many more unti
    we realized that many could be collapsed. We THINK that these methods suffice to
    solve any muffin problem. We have thought that before and been wrong.

    bill g.

Trackbacks

  1. The Muffin Problem – Site Title

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s