# The Muffin Problem

- Published in 2017
- Added on

In the collections

You have $m$ muffins and $s$ students. You want to divide the muffins into pieces and give the shares to students such that every student has $\frac{m}{s}$ muffins. Find a divide-and-distribute protocol that maximizes the minimum piece. Let $f(m,s)$ be the minimum piece in the optimal protocol. We prove that $f(m,s)$ exists, is rational, and finding it is computable (though possibly difficult). We show that $f(m,s)$ can be derived from $f(s,m)$; hence we need only consider $m\ge s$. For $1\le s\le 6$ we find nice formulas for $f(m,s)$. We also find a nice formula for $f(s+1,s)$. We give a function $FC(m,s)$ such that, for $m\ge s+2$, $f(m,s)\le FC(m,s)$. This function permeates the entire paper since it is often the case that $f(m,s)=FC(m,s)$. More formally, for all $s$ there is a nice formula $FORM(m,s)$ such that, for all but a finite number of $m$, $f(m,s)=FC(m,s)=FORM(m,s)$. For those finite number of exceptions we have another function $INT(m,s)$ such that $f(m,s)\le INT(m,s)$. It seems to be the case that when $m\ge s+2$, $f(m,s)=\min\{f(m,s),INT(m,s)\}$. For $s=7$ to 60 we have conjectured formulas for $f(m,s)$ that include exceptions.

## Links

## Other information

- key
- TheMuffinProblem
- type
- article
- date_added
- 2018-01-30
- date_published
- 2017-06-10

### BibTeX entry

@article{TheMuffinProblem, key = {TheMuffinProblem}, type = {article}, title = {The Muffin Problem}, author = {Guangiqi Cui and John Dickerson and Naveen Durvasula and William Gasarch and Erik Metz and Naveen Raman and Sung Hyun Yoo}, abstract = {You have {\$}m{\$} muffins and {\$}s{\$} students. You want to divide the muffins into pieces and give the shares to students such that every student has {\$}\frac{\{}m{\}}{\{}s{\}}{\$} muffins. Find a divide-and-distribute protocol that maximizes the minimum piece. Let {\$}f(m,s){\$} be the minimum piece in the optimal protocol. We prove that {\$}f(m,s){\$} exists, is rational, and finding it is computable (though possibly difficult). We show that {\$}f(m,s){\$} can be derived from {\$}f(s,m){\$}; hence we need only consider {\$}m\ge s{\$}. For {\$}1\le s\le 6{\$} we find nice formulas for {\$}f(m,s){\$}. We also find a nice formula for {\$}f(s+1,s){\$}. We give a function {\$}FC(m,s){\$} such that, for {\$}m\ge s+2{\$}, {\$}f(m,s)\le FC(m,s){\$}. This function permeates the entire paper since it is often the case that {\$}f(m,s)=FC(m,s){\$}. More formally, for all {\$}s{\$} there is a nice formula {\$}FORM(m,s){\$} such that, for all but a finite number of {\$}m{\$}, {\$}f(m,s)=FC(m,s)=FORM(m,s){\$}. For those finite number of exceptions we have another function {\$}INT(m,s){\$} such that {\$}f(m,s)\le INT(m,s){\$}. It seems to be the case that when {\$}m\ge s+2{\$}, {\$}f(m,s)=\min\{\{}f(m,s),INT(m,s)\{\}}{\$}. For {\$}s=7{\$} to 60 we have conjectured formulas for {\$}f(m,s){\$} that include exceptions.}, comment = {}, date_added = {2018-01-30}, date_published = {2017-06-10}, urls = {http://arxiv.org/abs/1709.02452v2,http://arxiv.org/pdf/1709.02452v2}, collections = {Easily explained,Food,Protocols and strategies}, url = {http://arxiv.org/abs/1709.02452v2 http://arxiv.org/pdf/1709.02452v2}, year = 2017, urldate = {2018-01-30}, archivePrefix = {arXiv}, eprint = {1709.02452}, primaryClass = {math.CO} }