[latexpage] Imagine, you and two friends visit a bakery and buy six delicious cupcakes. However, while leaving the bakery, your friend who’s holding the box with delicacies trips and one of the cupcakes falls to the ground. All three puzzled, you look at each other, how are you going to divide five cupcakes over three people? The smaller the pieces, the bigger the chance the piece will crumble. Hence you and your friends are challenged to divide the five cupcakes over three people such that everyone receives an equal cut and the smallest piece is as large as possible. This is a famous example of the Muffin Problem, first thought up by Alan Frank, a software-developer with a soft spot for mathematical puzzles. After the problem was published in The New York Times, it opened the door for a more general problem. There are $m$ muffins and $s$ students and every student should receive $\frac{m}{s}$ part of the muffins. How should you divide the muffins such that the smallest part is as large as possible? When we have five muffins and three students, a first guess would be to divide the five muffins as above. All three students get one muffin each and the remaining two are divided into portions of $\frac{1}{3}$ and $\frac{2}{3}$. We now have that the smallest piece is $\frac{1}{3}$. Is it possible to find a better solution? Yes, this is possible. One muffin should be divided in half, and the remaining four muffins should be divided into portions of $\frac{5}{12}$ and $\frac{7}{12}$. One student receives four parts of $\frac{5}{12}$ and the other two receive two portions of $\frac{7}{12}$ and half a muffin. How do we know there is not a better solution? Therefore we need three muffin-principles:
- Muffin-principle 1: if a muffin is cut into three parts, the smallest part has at most a size of $\frac{1}{3}$.
- Muffin-principle 2: if ten muffin parts are divided over three students, one student has at least four parts.
- Muffin-principle 3: if one student receives four parts with a total size of $\frac{5}{3}$, the smallest part has at most a size of $\frac{5}{3}$ x $\frac{1}{4}$ = $\frac{5}{12}$.
We assume that every muffin is cut into at least two pieces (if a student receives a complete muffin we can still assume that this muffin consists of two halves.) Then we have two possibilities to divide all five muffins. The first possibility is that at least one muffin is cut into three pieces. According to muffin-principle 1, the smallest part is now given by at most $\frac{1}{3}$, which is smaller than $\frac{5}{12}$, hence this is not a better solution. The second option is that all muffins are parted into two pieces, hence we obtain ten pieces in total. According to the second muffin-principle, in this case, one student should receive at least four parts and by muffin-principle 3 we conclude that the smallest part is now given by $\frac{5}{12}$. Hence we find that the smallest part will always be at most $\frac{5}{12}$.
Over the last few years, mathematician William Gasarch and his team have tried to find a general formula to solve the problem for $m$ muffins and $s$ students. So far they have not succeeded. Let’s take a look at the problem at hand. We can define $x_{i,j} \in [0,1]$ as the fraction of muffin $i$ assigned to student $j$ and
\[
\delta_{i,j} = \left\{ \begin{array}{ll}
1 \text{ if } x_{i,j} > 0\\
0 \text{ if } x_{i,j} = 0
\end{array}
\right.
\]
The problem can be defined as:
\begin{align*}
\text{max } & z\\
\text{subject to } & \sum_i x_{i,j} = \frac{m}{s} \quad \forall j\\
& \sum_j x_{i,j} = 1 \quad \forall i\\
& x_{i,j} \leq \delta_{i,j}\\
& z \leq x_{i,j} + (1-\delta_{i,j})\\
& 0 \leq x_{i,j}\leq 1\\
& \delta_{i,j} \in \{0,1\}
\end{align*}
Even though Gasarch did not find a general answer to this problem, he and his team did conclude that if $m>s$ the smallest part will always be at least $\frac{1}{3}$. Over the years they also solved every case for which $m\leq70$ and $s\leq60$. They also succeeded in finding a few formulas to calculate the optimal value for specific cases. Take for example the case of three students and where $m$ equals a multiple of three plus one. For example four, seven or ten. Then the smallest piece that is as big as possible is given by $\frac{(m-2)}{(2m-2)}$. In the case that the number of muffins is given by a multiple of three plus two, the smallest part will have size $\frac{m}{(2m+2)}$.
For now, finding a general formula would be a dream come true. Researchers believe that the key to a general formula lies somewhere in the ratio between m and s. This would mean that the solution to a problem with $m=54$ and $s=18$ equals the solution of a problem with $m=27$ and $s=9.$ However, it’s all still guesswork for now. So if you ever find yourself with a lot of time on your hands, take a shot at the Muffin Problem and maybe you’ll solve one of the sweetest mathematical puzzles.
This article is written by Fenna Beentjes
