The Muffin Problem

Definition Let there be $m$ muffins and $s$ students. The problem is to divide the muffins into pieces where every student gets exactly $\frac m s$ muffin, such that the size of the smallest piece you created while cutting the muffins is as large as possible.

Example For 3 students and 5 muffins, you could cut one muffin in half and the rest in $\frac 5 {12} + \frac 7 {12}$. Two students both get $\frac 1 2 + \frac 7 {12} + \frac 7 {12}$, the other student gets $\frac 5 {12} + \frac 5 {12} + \frac 5 {12}+ \frac 5 {12}$. Now the size of the smallest piece is $\frac 5 {12}$ which is larger than $\frac 1 3$ which corresponds to the trivial solution of cutting each muffin in three equal pieces.

The case of 5 students and 7 muffins

By trial and error we have found a solution where the size of the smallest piece is 1/3. In tabular form:

\begin{array}{r|ccccc} \text{Muffin}\backslash \text{Student} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1 &&&& \\ 2 & \frac 6 {15} & \frac 9 {15} &&& \\ 3 && \frac 7 {15} & \frac 8 {15} && \\ 4 && \frac 5 {15} & \frac 5 {15} & \frac 5 {15} & \\ 5 &&& \frac 8 {15} & \frac 7 {15} & \\ 6 &&&& \frac 9 {15} & \frac 6 {15} \\ 7 &&&&& 1 \\ \end{array} Notice the symmetry, and that one muffin is cut into three pieces which makes $\frac 1 3$ the smallest piece.

I happen to have looked in the original muffin paper by William Gasarch and page 160 reveils that $\frac 1 3$ is indeed optimal. (Note they have found no general formula yet, they only did some special cases.)

Question We now have a solution for this linear optimization problem, but how can we prove this solution is optimal?

Proof for 3 students and 5 muffins

The Muffin problem was coined in 2009 by Alan Frank, and a small article about this problem appeared recently in the Dutch newspaper NRC, following a muffin talk by Gasarch earlier this year. It contained a proof that for 3 students and 5 muffins, the solution of $\frac 5 {12}$ I gave above is optimal. I have tried to rewrite it leaving out all the pictures of muffins:

Proof We can assume that every muffin is cut into at least two pieces, because since at least one muffin has to be cut the smallest piece is at most $\frac 1 2$, so any entire muffin can be viewed as cut into two equal halves. There are two cases:

  1. Suppose there is at least one muffin being cut into 3 pieces. Then the smallest piece of that muffin is at most $\frac 1 3 < \frac 5 {12}$.

  2. Suppose all muffins are cut into exactly 2 pieces, so there are 10 pieces to be divided over 3 students. Therefore at least one student gets at least 4 pieces. Of those pieces, the smallest piece is at most $\frac 1 4 \cdot \frac 5 3 = \frac 5 {12}$.

PS Tagging MIP because Gasarch apparently claimed they used theorems from that field.

PPS My lecturer also found $\frac 1 3$ by rewriting it as a linear optimization problem and programming it in Sage, in itself an interesting task.

PPPS Fun fact, proven by Gasarch: when you have more muffins than students, the smallest piece is at least $\frac 1 3$.

Obviously I tried rewriting the proof for 3 students and 5 muffins, but I found it will have to have more cases because as the solution shows a muffin can be cut into 3 pieces without creating problems. But I couldn't figure out what to base the cases on. At least I found that if you cut all muffins into 2 pieces, you have 14 pieces so at least one student gets at most 2 pieces.

  • The problem is still unclear for me. The $s$ is not defined in the Definition. The solution $x=1/3$ is a solution for what? How is $x$ related to the division process, do the students get the same fractional amount? Is there any reference so that one can understand the problem?! (An engine search gave me a lot of references where the problem is stated for those that already know the problem and the research on it.) – dan_fulea Oct 16 at 17:17
  • @dan_fulea I'm sorry, I had indeed forgotten the $s$ in the definition. To be more precise, I have clarified that we are talking about the size of the smallest piece. The definition already says that every student gets the same amount ($\frac m s$) of muffin. I actually referenced the muffin paper, which also explains all of this. Are you saying that the proof of this is already known by a lot of people? Please point me to one of your references, in that case! – PHPirate Oct 16 at 17:34
  • I saw the question before, and i remember, i had problems to understand the cut + assembly procedure. This time i also had problems to digest, it was for instance unclear for me that the optimal solution is the maximal size of the minimal piece in a cut-in-pieces strategy which allows the pieces to be reassembled in blocks of mass $m/s$. The example had no reference to $m,s$. The example / [ hidden complete cutting solution] had no direct connection to the [optimal solution] which is $1/3$. It was too much, my interest was/is only related to possible arithmetic relation... – dan_fulea Oct 16 at 18:36
up vote 1 down vote accepted

Doesn't your comment at the end answer the question: "at least one student gets at most 2 pieces"?

  1. Since at least one muffin is cut, we can assume they all are.
  2. In order to beat 1/3, we must have each muffin cut into 2 pieces.
  3. 7 muffins cut into 2 pieces = 14 pieces
  4. 14 pieces distributed among 5 students, means at least one student gets at most 2 pieces
  5. 2 pieces totaling 7/5 means at least one of the pieces has size at least 7/10
  6. This piece of size at least 7/10 comes from a muffin whose other piece has size at most 3/10 < 1/3

Therefore, 1/3 is the best we can do. This argument works for any (m, s) with $4/3 \le m/s < 3/2$.

  • 1
    Oh you're right, I didn't realise that in step 1: suppose a muffin isn't cut, assume it is cut into two equal pieces that are given to the same person. So they are all cut. It seems to work out! Interesting last remark, I think you mean that if you distribute $2m$ pieces over s students such that $2m < 3s \iff m/s < 3/2$ then you have that at least one student gets at most 2 pieces (step 4) and if also $1- m/(2s) \le 1/3 \iff 4/3 \le m/s$ then you have step 6. – PHPirate Oct 19 at 8:30

This is trivial with mixed integer optimization and Yalmip (code shared below). I use binmodel to automatically convert the product of a binary and a continuous variable to linear expressions.

The solution is found in just a few seconds with cplex and reveals $t=1/3$.

m = 7; % number of muffins
s = 5; % number of students
p = 4; % maximum number of pieces per muffin

t = sdpvar(1);      % size of the smallest piece
x = sdpvar(m,p);    % x_{ij} is the size of piece j of muffin i
y = binvar(m,p);    % y_{ij} = 1 if muffin i is cut into j pieces
z = binvar(m,p,s);  % z_{ijk} = 1 if piece j of muffin i goes to student k


F =     [0 <= x <= 1];
F = F + [sum(x,2) == 1];
F = F + [sum(y,2) == 1];
F = F + [sum(z,3) == 1];
for k = 1:s
    F = F + [ sum(sum(x.*z(:,:,k))) == m/s ];
end
ysum = cumsum(y,2);
F = F + [x(:,2:end) <= 1-ysum(:,1:end-1)];
F = F + [t <= x + [zeros(m,1) ysum(:,1:end-1)]];

F = binmodel(F);

optimize(F,-t);
  • That's a great practical solution! Much easier than proving by hand, I see now. I knew Matlab had an optimization toolbox, but I didn't know Yalmip. I just installed it and cplex from IBM and it works, I like it. – PHPirate Oct 16 at 19:25
  • I noticed there is a slightly shorter formulation at yetanothermathprogrammingconsultant.blogspot.com – LinAlg Oct 17 at 15:22
  • Thanks for the link! I see he published today and has listed this question as reference, I hope he liked your solution :) (unless he and you are the same person ;) ) – PHPirate Oct 17 at 15:37
  • @PHPirate what makes his solution superior is that he does not need a $p$ parameter – LinAlg Oct 17 at 15:42
  • That's true, although when there are more muffins than students we can set $p=3$ and it's no restriction. – PHPirate Oct 17 at 15:44

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.