The Muffin Problem

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

conjecture

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