The Muffin Problem

• Published in 2017
• Added on 2018-01-30

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

• http://arxiv.org/abs/1709.02452v2
• http://arxiv.org/pdf/1709.02452v2

Other information

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-03-06},
	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}
}