Muffin Puzzle Solution (last updated July 14, 2019)

On July 3, I challenged readers of my Big Internet Math-Off pitch to try to find the way to divide 24 muffins among 25 people that makes the smallest piece as large as possible.

The best solution has smallest piece of size 8/25. Correct solutions were sent in by William Gasarch, Scott Huddleston, Evan Romer, and Andrew Stacey. Romer's solution was the most elegant, but Gasarch's solution was the most comprehensive: not only did he show that f(24,25) = 8/25, but he also showed that f(3k,3k+1) = k/(3k+1) for all positive integers k. Even more, he showed that f(3k+1,3k+2) = (2k+1)/(6k+4) and f(3k+2,3k+3) = (k+1)/(3k+3) = 1/3 for all k.

Here's Evan Romer's solution.

Here's William Gasarch's solution.

It now appears that the full Muffin Problem may have been solved by Scott Huddleston sometime around 2010; he found a quick algorithm for computing f(m,s) whose output appears to give the correct answer in all cases, but a proof has never been written down. Working independently, Richard Chatwin found an algorithm similar to (or perhaps identical to) Huddleston's and has written up his work in a draft that is being vetted by Gasarch and others. I hope to have more to say about this in a Mathematical Enchantments essay later this year.

Meanwhile, Gasarch is in the final stages of preparing a book on the Muffin Problem, to be published by World Scientific later this year. I will add information as it becomes available. (He did put an article on the arXiv a while ago, but he writes that the article "is out of date and wrong in some places, so not recommended".)

If any of you want to study the muffin function f(m,s), here is a list of triples {m,s,f(m,s)} with m > s, courtesy of Daniel Smolyak. (This doesn't cover cases with m < s like the case f(24,25), but duality gives us the value in those cases as well.) I did a number of plots of the muffin function, supporting Chatwin's claim that the function is a mix of piecewise-linear behavior and fractal behavior, continuous at some points and discontinuous at others.

William Gasarch has withdrawn his arXiv article on the Muffin Problem, but there are still two documents on the web that you can look at if you want to learn about his group's work:
FUN with Algorithms Conference:
http://drops.dagstuhl.de/opus/volltexte/2018/8806/pdf/LIPIcs-FUN-2018-15.pdf
SIGACT News Survey:
https://www.cs.umd.edu/users/gasarch/papers/sigmuffins.pdf
(The first page will look like it's by Lane Hemaspaandra. He is the editor of the Complexity Column. Gasarch and his co-authors are listed on the next page.)