How to prove that 1/3 is the optimal solution for the muffin problem with 5 students and 7 muffins?

Question

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.

Answer 1

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$.

Answer 2

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);