The Muffin Curse

Here’s a small puzzle that opens the door to a surprisingly tricky general problem: How can a teacher divide 24 muffins among 25 students so that everyone gets the same amount to eat but nobody gets stuck with any tiny pieces?

To get a clearer sense of what counts as a good answer, let’s consider a bad answer. You could remove 1/25th of each muffin, give an almost-complete muffin to each of the first 24 students, and give the 24 slivers to the last student. Then everyone gets 96% of a muffin, but it‘s a pretty crumby scheme for the student who gets nothing but slivers. We’d like to do better. Can you find a scheme in which the smallest piece anyone gets stuck with is bigger than 1/25 of a muffin? Can you find a solution in which the smallest piece is a lot bigger? After you’ve found the best solution you can and you can’t improve it, how might you try to prove that it’s the best solution anyone could ever find? And how would you solve the problem if there were a different number of muffins and/or a different number of students trying to share them? Puzzles of this kind can be challenging and addictive, and the general solution wasn’t found until last year.

The Muffin Problem was invented in 2008 by a friend of mine, the recreational mathematician Alan Frank. He asked: If we have m muffins to be divided among s students, how can we cut up the muffins and apportion the pieces so that each student gets m/s of a muffin, and so that the smallest piece is as large as possible? (Making sure that even the smallest piece is large ensures that all the pieces are large. Kind of like saying “A society is only as rich as its poorest citizens.”) Let’s define f(m,s) to be the largest number f for which there’s a scheme in which all the pieces are of size at least f. (Here “f” is for “function”, “fraction”, and “Frank”.) 

Alan was inspired by a real-world problem involving fewer than 24 muffins and fewer than 25 muffin-eaters. In fact, there were just two muffin-eaters, his children, but in dividing up an odd number of muffins between the two kids he began to think about the general case, in the way that a mathematician does. I’m illustrating his problem using the numbers 24 and 25 as an homage to the classic children’s book “The Math Curse” about the math problems that lurk everywhere around us, just waiting for someone like Alan to notice them. Author Jon Scieszka and illustrator Lane Smith raise the problem of how one should share 24 cupcakes among 25 people. Their way of solving the problem contains much practical wisdom, but it dodges the problem of how one should share the cupcakes if one must.

From “The Math Curse”, by Jon Scieszka and Lane Smith. Permission pending.

I’ve challenged you to find f(24,25). We already know that f(24,25) is at least 1/25 because that’s the size of the smallest piece in the “crumby scheme”, but surely you can do better. It’s also not hard to prove that f(24,25) is less than 1/2. You can find the solution to the f(24,25) problem in Endnote #1.

TRICKIER THAN IT LOOKS

As an illustration of how tricky sharing muffins can be, here’s the best scheme for dividing seven muffins four ways. Split six of the seven muffins into a piece of size 7/12 and a piece of size 5/12 and split the seventh into two equal parts of size 1/2 (which I’ll write as 6/12 to give all the fractions a common denominator). Two of the students each get three pieces of size 7/12 while the other two students each get three pieces of size 5/12 and one piece of size 6/12. Here’s a depiction of the scheme in which the seven rows not including the bottom row correspond to the seven muffins and the four columns to the right of the equals-signs correspond to the four students.The smallest piece in this scheme is 5/12 of a muffin, so f(7,4) is at least 5/12. In fact, it can be proved that you can’t beat this, so f(7,4) is exactly 5/12.

My favorite fact about the muffin problem is the “muffin duality law” first noticed by mathematician Erich Friedman:

f(s,m) = (s/m) f(m,s),

or in its most symmetrical form,

m f(s,m) = s f(m,s).

Duality tells us that there’s a relationship between the problem of dividing 24 muffins among 25 students and the seemingly unrelated problem of dividing 25 muffins among 24 students. This symmetry between muffins and students seems strange, since students are eager to eat muffins while muffins are neither eager to eat students nor eager to be eaten by them (despite what the muffin in The Muffin Song says). Yet the formula is true and easy to prove.

To see via an example why the duality relation holds, notice that if we take the table given above depicting our sharing-scheme for the 7-muffin, 4-student problem, in which rows sum to 1 and columns sum to 7/4, and we flip it diagonally so that rows become columns and columns become rows, we get a table in which rows sum to 7/4 and columns sum to 1; if we then multiply every number in sight by 4/7, we get a table in which rows sum to 1 and columns sum to 4/7. That is, we get a sharing-scheme for the 4-muffin, 7-student problem! What’s more, the size of the smallest piece in the new sharing-scheme is exactly 4/7 times the size of the smallest piece in the old sharing-scheme. And this relationship is a two-way street: each scheme for the 7-muffin, 4-student problem gives a scheme for the 4-muffin, 7-student problem and vice versa.

HISTORY OF THE PUZZLE

Alan told me about the problem in 2008. I proceeded to share it with the math-fun forum that both Erich Friedman (mentioned above) and I belong to, and the problem quickly went viral in the math-puzzle community. In many forums the puzzle appeared without attribution. This is a shame; we should acknowledge the people who invent new puzzles if we want to motivate people to continue to invent them!

One person who saw the puzzle was Jeremy Copeland, who mentioned the problem to Gary Antonick, who published the puzzle (with cupcakes replacing muffins) in his New York Times Numberplay column. Richard Chatwin saw the column and contacted Antonick who put him in touch with me, and I shared with Richard what I knew. Richard was intrigued but eventually put the problem aside without solving it.

In 2016, computer scientist and mathematician William Gasarch attended the biennial Gathering 4 Gardner conference in Atlanta and saw a booklet of fun math puzzles compiled by Julia Robinson Math Festival founder and director Nancy Blachman. One of the puzzles was Alan Frank’s Muffin Problem. Gasarch quickly got hooked and enlisted some undergraduates to help him study the muffin function f(m,s). He reported his progress at the next Gathering 4 Gardner in 2018:

In that same year Richard Chatwin returned to the fray and independently found an efficient method for computing f(m,s), unaware that math-fun subscriber Scott Huddleston had found the same method back in 2010. In 2019, Chatwin was able to construct a proof that the method always gives the optimal solution (see Chatwin’s article listed in the References). Gasarch was in the process of publishing a book about the muffin problem coauthored with several of his students (see the References); he delayed publication so that the book could discuss the long-sought solution.

Alan Frank’s Muffin Problem fits into existing literature on dissection puzzles. Some problems of this kind were popular in ancient Greece, such as the Ostomachion. A more recent dissection puzzle is the “Haberdasher’s Puzzle” of Henry Dudeney. Dudeney asked solvers to divide an equilateral triangle into as few pieces as possible in such a way that the pieces can be arranged to form a square. The problem appeared in a popular magazine of the day, and while many readers found five-piece dissections, only one reader found the four-piece dissection shown in Endnote #2.

The Muffin Problem can be seen as a one-dimensional dissection puzzle where we are trying to dissect a collection of m line segments of length 1 into a collection of s line segments of length m/s. Or, if we prefer a more symmetrical version of the problem (as the duality law invites us to adopt), we can rescale the problem and cast it as a problem about dissecting a collection of m line segments of length 1/m into a collection of s line segments of length 1/s. Or, if you prefer, a problem of dissecting a collection of m line segments of length s into a collection of s line segments of length m. In any case, what’s novel about Alan’s one-dimensional dissection problem is that, instead of minimizing the number of pieces, we’re supposed to maximize the size of the smallest piece.

INTO THE FUTURE

The muffin problem may be solved in the sense that we now have a validated algorithm for computing f(m,s) for any m and s we like, but the story isn’t over. Once we’ve taken the symmetrical point of view, there’s no reason to limit ourselves to just two variables m and s. Here’s an example of the sort of variant Huddleston is currently considering: if we have to divide the number 1 into fractions that can be organized into 3 groups that each add up to 1/3, and can be organized into 5 groups that each add up to 1/5, and can be organized into 7 groups that each add up to 1/7, how can we make the smallest of the fractions as big as possible?

An intriguing aspect of the original problem is that f(m,s) turns out only to depend on the ratio m/s.  This is far from obvious to me. For instance: I can see that any good solution to the m=7, s=4 puzzle gives a solution to the m=14, s=8 puzzle that’s at least as good, since I can divide the 14 muffins into two groups of 7 and apply the m=7, s=4 solution to each set. So f(14,8) can’t be smaller than f(7,4). But I might hope that the (14,8) problem gives me room to find a slightly better solution. That is, I might hope that f(14,8) is slightly bigger than f(7,4). Chatwin’s proof shows that it isn’t, but I’d love to know a simpler proof.

Since f(m,s) depends only on the ratio m/s, we can define g(r) for any positive rational number r as f(m,s) where m/s = r. For instance, we define g(3/10) as the common value of f(3,10), f(6,20), f(9,30), … (For half-baked speculation about how we might define g(r) when r is irrational, see Endnote #3.) This function g(r) encodes all the information you need to solve muffin problems: to find f(m,s), just compute g(m/s). But the function g is a rather strange beast. It’s well-behaved on some intervals but extremely erratic on others. Here’s a rough plot of what g(m/s) looks like for values of m/s between 1 and 10:

And here’s a zoom showing g(m/s) for values of m/s between 1.00 and 1.09:

These are just two of the fourteen snapshots of the graph of g(m/s) that I created using a table of data provided by Gasarch’s students. With these pictures you can appreciate how complicated f(m,s) is, and you can see why it took so much time, and so many people, to solve the muffin problem!

Thanks to Richard Chatwin, Alan Frank, William Gasarch, Sandi Gubin and Evan Romer.

Next month: How Can Math Be Wrong?

ENDNOTES

#1. The best solution has smallest piece of size 8/25. I posted this puzzle as a challenge in the Big Internet Math-Off in the summer of 2019; what follows is a slightly adapted version of the solution I received from reader Evan Romer.

Divide the first four muffins as follows:

12/25 + 13/25
11/25 + 14/25
10/25 + 15/25
9/25 + 8/25 + 8/25

Reassemble these pieces into:

13/25 + 11/25
14/25 + 10/25
15/25 + 9/25

leaving 12/25, 8/25, 8/25 left over.

Do this again, five more times (six times in total).

So we’ve used all 24 muffins, and have made eighteen reassembled muffins, 24/25 each.
And we have six 12/25 pieces left over, which make three reassembled muffins.
And we have twelve 8/25 pieces left over, which make four reassembled muffins.
This gives us 18+3+4=25 reassembled muffins, each 24/25 of an original muffin.
The smallest piece was 8/25.

Here’s a proof by contradiction that 8/25 is the best you can do:

Assume that the smallest piece is (8+a)/25, for some a>0.

Note 0: Every reassembled muffin will be 24/25 of a muffin. And of course every original muffin is 25/25 of a muffin.

Note 1: The assumption implies that every reassembled muffin consists of two pieces only: if a reassembled muffin had three pieces, it would be at least 3×(8+a)/25, which is more than 24/25.

Note 2: If an original muffin has a piece taken out of it that is greater than (9−2a)/25, then the remainder must be a single piece: for if the remainder were in two or more pieces, the pieces would add up to more than (9−2a)/25 + 2×(8+a)/25 = 25/25.

Note 3: a cannot be greater than 4: for if we had a>4, then the smallest piece would be > 12/25, so every reassembled muffin would be > 2×12/25.

Some reassembled muffin has a piece that’s (8+a)/25, so its other piece must be (16−a)/25.
But if an original muffin had (16−a)/25 cut from it, this satisfies the hypothesis of Note 2 because (16−a)/25 > (9−2a)/25, so the remainder must be a single piece, so its other piece would be (9+a)/25.
So some reassembled muffin is (9+a)/25 plus (15−a)/25.
But if an original muffin had (15−a)/25 cut from it, this satisfies the hypothesis of Note 2 because (15−a)/25 > (9−2a)/25. So some original muffin is (15−a)/25 plus (10+a)/25.
… and so on …
So some reassembled muffin is (15+a)/25 plus (9−a)/25.
But if an original muffin had (9−a)/25 cut from it, this satisfies the hypothesis of Note 2 because (9−a)/25 > (9−2a)/25.
So some original muffin is (9−a)/25 plus (16+a)/25.
So some reassembled muffin is (16+a)/25 and (8−a)/25.

But now we have a piece smaller than (8+a)/25, contradicting our assumption.

Here is Bill Gasarch’s solution.

#2. Here’s the four-piece dissection published by Dudeney:

Henry Dudeney’s solution to the “haberdasher problem”, taken from https://en.wikipedia.org/wiki/Dissection_puzzle . Permission pending.

Here’s a nice video from frequent Gathering 4 Gardner attendee Tim Rowett about the Dudeney dissection:

#3: It’s natural to wonder whether the magic function g(r) (the one that tells you the value of f(m,s) by way of the formula f(m,s) = g(m/s)) can be extended to values of r that are irrational. Here’s a proposed variant of the muffin problem that might relate to this question. Imagine an infinite supply of 1-ounce chocolates rolling off an assembly line that’s staffed by two immortal and indefatigable employees (call them Ethel and Lucy) who have to feed an infinite line of students. When a new chocolate arrives, Ethel cuts it up into smaller morsels and puts the morsels into an infinitely large holding area; meanwhile, Lucy takes morsels from the holding area and hands them out to students. Each morsel must eventually be given to some student (even if it spends millions of years in the holding area), and each student must get exactly x ounces of chocolate (even if she has to wait millions of years to get it). If Lucy and Ethel want the smallest morsel any student gets to be as large as possible, what goal should they shoot for, as a function of x? I’m pretty sure that when x is rational, this is just our friend g(x) [nope, I was wrong; see the UPDATE below]. But what happens when x is irrational? If, say, x is the golden ratio ϕ = (1 + sqrt(5))/2 = 1.618…, is there a way for Ethel to divide the 1-ounce chocolates into smaller morsels, and for Lucy to distribute the morsels, so that every morsel gets eaten, and every student gets exactly ϕ ounces of chocolate, and no morsel is less than 0.4 ounces?

UPDATE: Evan Romer points out that for any x between 1 and 2 we can divide each chocolate of size 1 into a piece of size x−1 and a piece of size 2−x and then reassemble them to form infinitely many pieces of size (x−1)+(x−1)+(2−x) = x. In assembly-line terms, the holding area will get more and more crowded, but every piece added to it will eventually get handed to a student. In the case x = 1.618.., the smallest piece has size 1−x = 0.382…, which is unfortunately just a hair smaller than 0.4. Can anyone beat 0.382…? Can anyone achieve 0.4? [Yes! See Yoav Kallus’ solution in the Comments.]

REFERENCES

Richard Chatwin, An optimal solution for the muffin problem, https://arxiv.org/pdf/1907.08726.pdf.

William Gasarch, Erik Metz, Jacob Prinz, and Daniel Smolyak, Mathematical Muffin Morsels: Nobody wants a small piece. World Scientific, 2020. See also the companion website www.cs.umd.edu/users/gasarch/MUFFINS/muffins.html .