I've been meaning to post on THE MUFFIN PROBLEM for at least a year. Its a project I've been working on for two years, but every time I wanted to post on it I thought.
I'm in the middle of a new result. I'll wait until I get it!
However, I was sort of forced to finally post on it since Ken Regan (with my blessing) posted on it. In fact its better this way- you can goto his post for the math and I get to just tell you other stuff.
The problem was first defined by Alan Frank in a math email list in 2009.
I'll define the problem, though for more math details goto Ken's post: here
You have m muffins and s students. You want to give each student m/s piece and
divide the muffins to maximize the min piece. Let f(m,s) be the size of the min piece
in an optimal divide-and-distribute procedure.
Go and READ his post, or skim it, and then come back.
Okay, you're back. Some informal comments now that you know the problem and the math
1) I saw the problem in a pamplet at the 12th Gathering for Gardner. Yada Yada Yada I have 8 co-authors and 200 pages, and a paper in FUN with algorihtms You never know when a problem will strike you and be worth working on!
(The 8 coauthors are Guangiqi Cui, John Dickerson, Naveen Dursula, William Gasarch, Erik Metz,
Jacob Prinze, Naveen Raman, Daniel Smolyak, Sung Hyun Yoo. The 200 pages are here
. The FUN with algorithms paper, only 20 pages, is here
2) Many of the co-authors are HS students. The problem needs very little advanced mathematics (though Ken thinks it might connect to some advanced math later). This is a PRO (HS students can work on it, people can understand it) and a CON (maybe harder math would get us more unified results)
3) The way the research had gone is a microcosm for math and science progress:
We proved f(m,s) = (m/s)f(s,m) (already known in 2009) by Erich Friedman in that math email list)
Hence we need only look at m>s.
First theorem: we got a simple function FC such that
f(m,s) ≤ FC(m,s)
for MANY m,s we got f(m,s) = FC(m,s).
GREAT! - conjecture f(m,s) = FC(m,s)
We found some exceptions, and a way to get better upper bounds called INT.
GREAT! - conjecture f(m,s) = MIN(FC(m,s),INT(m,s))
We found some exceptions, and a way to get better upper bounds called ... We now have
f(m,s) = MIN(FC(m,s), INT(m,s), ERIK(m,s), JACOB(m,s), ERIKPLUS(m,s), BILL(m,s))
and it looks like we still have a few exceptions.
This is how science and math works- you make conjectures which are false but the refutations lead
to better and better results.
Also, we have over time mechanized the theorems, a project called:
Making Erik Obsolete
since Erik is very clever at these problems, but we would like to not have to rely on that.
4) I have worked hard on this problem as is clear from this: picture