\documentclass[a4paper,UKenglish]{lipics-v2018} %This is a template for producing LIPIcs articles. %See lipics-manual.pdf for further information. %for A4 paper format use option "a4paper", for US-letter use option "letterpaper" %for british hyphenation rules use option "UKenglish", for american hyphenation rules use option "USenglish" % for section-numbered lemmas etc., use "numberwithinsect" \usepackage{microtype}%if unwanted, comment out or use option "draft" \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\N}{\mathbb{N}} \newcommand{\aaa}[2]{a_{ #1 #2}} \newcommand{\bbb}[2]{b_{ #1 #2}} \newcommand{\x}[2]{x_{ #1 #2}} \newcommand{\y}[2]{y_{ #1 #2}} \newcommand{\third}[1]{\frac{{#1}}{3}} \newcommand{\swp}{s_{W+1}} \newcommand{\sw}{s_W} \newcommand{\mos}{\frac{m}{s}} \newcommand{\FC}{{\rm FC}} \newcommand{\INT}{{\rm INT}} \newcommand{\BUD}{{\rm BUD}} \newcommand{\BUDMAT}{{\rm BUDMAT}} \newcommand{\VLOWER}{{\rm VLOWER}} \newcommand{\CHEATALOT}{{\rm CHEATALOT}} \newcommand{\CHEATALITTLE}{{\rm CHEATALITTLE}} %\graphicspath{{./graphics/}}%helpful if your graphic files are in another directory \bibliographystyle{plainurl}% the recommnded bibstyle \title{A Muffin-Theorem Generator} \titlerunning{ }%optional, please use if title is longer than one line \author{Guangqi Cui}{Montgomery Blair High School}{bestwillcui@gmail.com}{ }{ }{ } \author{John Dickerson}{Department of Computer Science and UMIACS, Univ of MD at College Park}{john@cs.umd.edu}{ }{ }{ } \author{Naveen Durvasula} {Montgomery Blair High School} {140.naveen.d@gmail.com} { }{ }{ } \author{William Gasarch} {Department of Computer Science, Univ of MD at College Park} {gasarch@cs.umd.edu} { }{ }{ } \author{Erik Metz} {Department of Mathematics, Univ of MD at College Park (ugrad)} {emetz1618@gmail.com} { }{ }{ } \author{Jacob Prinz} {Department of Physics, Univ of MD at College Park (ugrad)} {jacobeliasprinz@gmail.com} { }{ }{ } \author{Naveen Raman} {Richard Montgomery High School} {nav.j.raman@gmail.com} { }{ }{ } \author{Daniel Smolyak} {Department of Computer Science (ugrad). Univ of MD at College Park} {dsmolyak@gmail.com} { }{ }{ } \author{Sung Hyun Yoo} {Bergen County Academies (a High School)} {sunnyyoo812@gmail.com} { }{ }{ } \authorrunning{G.\, Cui et al.}%mandatory. First: Use abbreviated first/middle names. Second (only in severe cases): Use first author plus 'et al.' \Copyright{ Guangqi Cui, John Dickerson, Naveen Durvasula, William Gasarch, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak, and Sung Hyun Yoo } %mandatory, please use full first names. LIPIcs license is "CC-BY"; http://creativecommons.org/licenses/by/3.0/ \subjclass{\ccsdesc[300]{Mathematics of Computing~Combinatorial Optimization}} % mandatory: Please choose ACM 2012 classifications from % https://www.acm.org/publications/class-2012 or https://dl.acm.org/ccs/ccs_flat.cfm %. E.g., cite as "General and reference $\rightarrow$ General literature" or % \ccsdesc[100]{General and reference~General literature}. \keywords{Fair Division, Theorem Generation}%mandatory \category{}%optional, e.g. invited paper \relatedversion{https://arxiv.org/abs/1709.02452} %optional, e.g. full version hosted on arXiv, HAL, or other respository/website \supplement{}%optional, e.g. related research data, source code, ... hosted on a repository like zenodo, figshare, GitHub, ... \funding{}%optional, to capture a funding statement, which applies to all authors. Please enter author specific funding statements as fifth argument of the \author macro. \acknowledgements{ We thank Nancy Blachman who compiled the list of problems that introduced us to this problem, Alan Frank who first came up with the problem. We would also like to thank Alan Frank, James Propp, and Sam Zbarsky for stimulating discussions of the topic. } %Editor-only macros:: begin (do not touch as author)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \EventEditors{Hiro Ito, Stephano Leonardi, Linda Pagli, and Giuseppe Prencipe} \EventNoEds{4} \EventLongTitle{9th International Conference on Fun with Algorithms (FUN 2018)} \EventShortTitle{FUN 2018} \EventAcronym{FUN} \EventYear{2018} \EventDate{June 13--15, 2018} \EventLocation{La Maddalena, Italy} \EventLogo{} \SeriesVolume{100} \ArticleNo{15} %\nolinenumbers %uncomment to disable line numbering %\hideLIPIcs %uncomment to remove references to LIPIcs series (logo, DOI, ...), e.g. when preparing a pre-final version to be uploaded to arXiv or another public repository %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle \begin{abstract} Consider the following FUN problem. Given $m,s$ you want to divide $m$ muffins among $s$ students so that everyone gets $\frac{m}{s}$ muffins; however, you want to maximize the minimum piece so that nobody gets crumbs. Let $f(m,s)$ be the size of the smallest piece in an optimal procedure. We study the case where $\ceil{\frac{2m}{s}}=3$ because (1) many of our hardest open problems were of this form until we found this method, (2) we have used the technique to {\it generate muffin-theorems}, and (3) we conjecture this can be used to solve the general case. We give (1) an algorithm to find an upper bound for $f(m,s)$ when $\ceil{\frac{2m}{s}}=3$ (and some ways to speed up that algorithm if certain conjectures are true), (2) an algorithm that uses the information from (1) to try to find a lower bound on $f(m,s)$ (a procedure) which matches the upper bound, (3) an algorithm that uses the information from (1) to generate muffin-theorems, and (4) an algorithm that we think works well in practice to find $f(m,s)$ for any $m,s$. \end{abstract} \section{Introduction} Consider the following FUN problem. Given $m,s$ you want to divide $m$ muffins among $s$ students so that everyone gets $\frac{m}{s}$ muffins; however, you want to maximize the minimum piece so that nobody gets crumbs. Let $f(m,s)$ be the size of the smallest piece in an optimal procedure. We give an example: \noindent {\it You have 47 muffins and 36 students. You want to divide the muffins evenly, but no student wants a small piece. Find a protocol that maximizes the smallest piece. We show in Section~\ref{se:47-36} that there is a procedure for this with smallest piece $\frac{31}{90}$ and that this is optimal. Hence $f(47,36)=\frac{31}{90}$. } \noindent {\bf Convention} When discussing a muffin being cut we refer to {\it pieces}. When discussing a student receiving we refer to {\it shares}. They are the same; however, it will be good to have different terminologies to focus on what's important. We treat a piece, a share, and its value as the same thing. So we may say {\it let $x\ge \frac{1}{3}$ be given to a student}. \begin{definition} Let $m,s\in\N$. An {\it $(m,s)$-protocol} is a protocol to cut $m$ muffins into pieces and then distribute them to the $s$ students so that each student gets $\frac{m}{s}$ muffins. An $(m,s)$-protocol is {\it optimal} if it has the largest smallest piece of any protocol. $f(m,s)$ is the size of the smallest piece in an optimal $(m,s)$-protocol. \end{definition} Clearly, for all $a\in\N$, $f(am,as)\ge f(m,s)$. All of our theorems indicate that $f(am,as)=f(m,s)$. We have not been able to prove this; however, we will only consider the cases where $m,s$ are relatively prime. We came upon this problem in a pamphlet {\it Julia Robinson Mathematics Festival: A Sample of Mathematical Puzzles} compiled by Nancy Blachman. On Page 2 was {\it The Muffin Puzzle} which asked about the problem for several particular cases. Nancy Blachman attributes the problem to Alan Frank and points out that it was described by Jeremy Copeland~\cite{muffin}. We are the first ones to consider this problem seriously for general $m,s$ with one caveat: There was some discussion of this problem in the math-fun email list in 2009. We have obtained a copy of their arxives and discovered that they already had Theorem~\ref{th:dual} and \ref{th:mip}. We will credit the individuals when we get to those theorems. Given $m,s$ how hard is it to compute $f(m,s)$? Computing $f(m,s)$ can be rephrased as a mixed integer program on $O(ms)$ variables (the proof is in the Section~\ref{se:mip}). Since the input is of size $O(\log m + \log s)$ this result does not even put the problem into NP. One of the upshots of this paper will be a procedure that we conjecture puts the computation of $f(m,s)$ into P. We study the case where $\ceil{\frac{2m}{s}}=3$ because (1) many of our hardest open problems were of this form until we found this method, (2) we have used the technique to {\it generate muffin-theorems}, (3) we conjecture this can be used to solve the general case. For $1\le s\le 50$, $1\le m\le 60$ we have computed $f(m,s)$. In this paper we focus on a subset of the material that lends itself to generating theorems about muffins via an algorithm. \section{Summary of Results} In Sections~\ref{se:basict},\ref{se:basicd} we give basic theorems and definitions used throughout the paper. In Section~\ref{se:47-36} we illustrate the {\it Buddy-Match techniques} by proving $f(47,36)\le \frac{31}{90}$. In Section~\ref{se:lower} we illustrate how to obtain lower bounds and present the result $f(47,36)\ge \frac{31}{90}$. In Sections~\ref{se:X} we discuss how to generate theorems from the Buddy-Match Technique. These theorems are of the form: \medskip {\it If $d\in \N$ and $1\le a\le 3d-1$, $a,d$ relatively primes, then $$(\forall k\ge 1)\biggl [f(3dk+a+d,3dk+a)\le \frac{dk+X}{3dk+a}\biggr ]$$} \medskip \noindent where $X$ is a constant which can depend on $a,d$ but not on $k$. In Section~\ref{se:gen} we discuss how to generate theorems that are more general. Here is an example: \newcommand{\ob}[1]{\frac{dk+{#1}}{3dk+a}} \medskip {\it If $1\le a\le \frac{5d}{7}$ and $a\ne \frac{2d}{3}$ then $f(3dk+a+d,3dk+a)\le \ob{X}$ where $X= \max \{\frac{2a}{5},\frac{a+d}{6} \}.$} \medskip In Sections~\ref{se:Xcheatsalittle},~\ref{se:Xcheatsalot} we show how, assuming certain conjectures, one can speed up the Buddy-Match Technique. In Section~\ref{se:finalalg} we give an algorithm that we conjecture puts $f(m,s)$ into P. In Section~\ref{se:open} we speculate about that algorithm and other muffin-issues. In the appendix we state and sometimes prove theorems that are needed to fill in some of the gaps in our narrative. We also give some examples of the theorems we generated. \section{Basic Theorems}\label{se:basict} In this section we prove two theorems that will enable us, for the rest of the paper, to only consider $m,s$ and protocols such that (1) $m>s\ge 3$, (2) $s$ does not divide $m$, and (4) every muffin is cut into exactly two pieces. The following theorem takes care of the cases $s=1$ and $s=2$. The proofs are easy and left to the reader. \begin{theorem}\label{th:easy}~ \begin{enumerate} \item $(\forall m)[f(m,1)=1]$ \item $(\forall m)[m\equiv 0\pmod 2\rightarrow f(m,2)=1]$ \item $(\forall m)[m\equiv 1\pmod 2\rightarrow f(m,2)=\frac{1}{2}]$ \item $(\forall m,s)[ s \hbox{ divides } m \rightarrow f(m,s)=1]$. \end{enumerate} \end{theorem} The following theorem shows that if you know $f(m,s)$ then you know $f(s,m)$. Combined with Theorem~\ref{th:easy} we need only consider $m>s\ge 3$. This theorem was independently discovered by Erich Friedman, within the math-fun email list, in 2009. \begin{theorem}\label{th:dual} Let $m,s\in\N$. Then $f(s,m)=\frac{s}{m}f(m,s)$. \end{theorem} \begin{proof} Assume $f(m,s)\ge \alpha$. We show $f(s,m)\ge \frac{s}{m}\alpha$. Let $M_1,\ldots,M_m$ be the muffins. Let $S_1,\ldots,S_s$ be the students. The protocol that achieves $f(m,s)\ge \alpha$ must be of the following form: \begin{enumerate} \item For each $1\le i\le m$ divide $M_i$ into pieces $(\aaa i 1, \aaa i 2,\ldots,\aaa i {m_i})$ where $\sum_{j=1}^{m_i} \aaa i j = 1$. \item For each $1\le j\le s$ give $S_j$ the shares $[\bbb 1 j, \bbb 2 j,\ldots,\bbb {s_j} j]$ where $\sum_{i=1}^{s_j} \bbb i j = \frac{m}{s}$. \end{enumerate} The following hold: \begin{itemize} \item $\bigcup_{i=1}^m \bigcup_{j=1}^{m_i} \{ \aaa i j \} = \bigcup_{j=1}^s \bigcup_{i=1}^{s_j} \{ \bbb i j \}$ \item The min over all of the $\aaa i j$ is $\alpha$. \end{itemize} The following protocol shows that $f(s,m) \ge \frac{s}{m}\alpha$. Let $M_1',\ldots,M_s'$ be the muffins. Let $S_1',\ldots,S_m'$ be the students. \begin{enumerate} \item For each $1\le j\le s$ divide $M_j'$ into $(\frac{s}{m}\bbb 1 j, \frac{s}{m}\bbb 2 j,\ldots,\frac{s}{m}\bbb {s_j} j )$. Note that $\sum_{i=1}^{s_j} \frac{s}{m}\bbb i j = \frac{s}{m}\sum_{i=1}^{s_j} \bbb i j = \frac{s}{m}\times\frac{m}{s}=1.$ \item For each $1\le i\le m$ give $S_j'$ $[\frac{s}{m}\aaa i 1, \frac{s}{m}\aaa i j,\ldots,\frac{s}{m}\aaa i {m_i} ]$. Note that $\sum_{j=1}^{m_i} \frac{s}{m} \aaa i j = \frac{s}{m}\sum_{j=1}^{m_i} \aaa i j = \frac{s}{m}\times 1 = \frac{s}{m}.$ \end{enumerate} Clearly this is a correct protocol and the minimum piece is of size $\frac{s}{m}\alpha$. We now show that $f(s,m)=\frac{s}{m}f(m,s)$. By the above we have both (1) $f(s,m) \ge \frac{s}{m} f(m,s)$, and (2) $f(m,s) \ge \frac{m}{s} f(s,m).$ Hence $$f(s,m) \ge \frac{s}{m} f(m,s) \ge \frac{s}{m} \frac{m}{s} f(s,m)= f(s,m).$$ Therefore $f(s,m)=\frac{s}{m}f(m,s)$. \end{proof} \begin{theorem}\label{th:uncut} Let $m,s\in\N$. \begin{enumerate} \item If $f(m,s)\ge\alpha$ and $\alpha>\frac{1}{3}$ via protocol P then protocol P cuts every muffin into 1 or 2 pieces. \item $f(m,s)\ge\alpha$ and $\alpha\le \frac{1}{2}$ via protocol P then there is a protocol P' such that (1) P' also yields $f(m,s)\ge \alpha$, and (2) P' cuts every muffin into 2 or more pieces. \end{enumerate} \end{theorem} \begin{proof} a) If any muffin is cut into $\ge 3$ pieces then there is a piece $\le \frac{1}{3} < \alpha$. \noindent b) If any muffin is uncut and given to (say) Alice then we can add a step where we cut the muffin into $(\frac{1}{2},\frac{1}{2})$ and give both $\frac{1}{2}$-sized pieces to Alice. Since $\alpha\le \frac{1}{2}$ adding in some pieces of size $\frac{1}{2}$ does not affect the smallest piece. \end{proof} By Theorem~\ref{th:uncut} we have the following convention. \noindent {\bf Convention:} When trying to show that $f(m,s)\le \alpha$ where $\frac{1}{3} < \alpha < \frac{1}{2}$ we will assume, by way of contradiction, that there is a protocol showing $f(m,s)>\alpha$ where every muffin is cut into exactly 2 pieces. \section{Basic Definitions}\label{se:basicd} \begin{definition}\label{de:buddy} Let $m,s\in\N$. Assume there is an $(m,s)$-protocol. \begin{enumerate} \item The two pieces that come from the same muffin are called {\it buddies}. $B(x)$ is the buddy of $x$. Note that $B(x)=1-x$. \item A student that gets $A$ shares is an {\it $A$-student}. A share given to an $A$-student is an {\it $A$-share}. \item 2-Shares that are given to the same 2-student are {\it matched}. $M(x)$ is the match of 2-share $x$. Note that $M(x)=\frac{m}{s}-x$. \item If $x$ is a share given to a 3-student then $M_S(x)$ is the smallest share (not including $x$) that the student has, and $M_L(x)$ is the largest. Note that $M_S(x) \le \frac{(m/s)-x}{2}$. Hence $B(M_S(x)) \ge 1-\frac{(m/s)-x}{2}$. \end{enumerate} \end{definition} \noindent {\bf Notation:} $(a,b)$ will mean the set of shares that have size strictly between $a$ and $b$. Hence $|(a,b)|$ will be the number of such shares. We use similar notation for $[a,b]$. \section{An Example is Worth A Thousand Theorems: 43 muffins, 39 Students}\label{se:47-36} \renewcommand{\ob}[1]{\frac{#1}{360}} \newcommand{\EE}[3]{e({#1},{#2},{#3})} The method we demonstrate in this section is called {\it The Buddy-Match Method}. \begin{theorem}\label{th:47-36} $f(47,36)\le \frac{31}{90}=\ob{124}$. \end{theorem} \begin{proof} To make the notation easier we write all fractions as having denominator $360$. Assume there is an $(47,36)$-procedure. We show that there is a piece $\le \ob{124}$. Note that $\frac{47}{36}=\ob{470}$. \noindent {\bf Case 1:} Some student gets $\ge 4$ shares. Then some students has a share $\le \frac{47}{36\times 4}<\ob{124}$. \noindent {\bf Case 2:} Some student gets $\le 1$ share. $1 <\frac{47}{36}$, so this is impossible. \noindent {\bf Case 3:} Every muffin is cut in 2 pieces and every student gets either 2 or 3 shares. The total number of shares is 94. Let $s_2$ ($s_3$) be the number of 2-students (3-students). \[ \begin{array}{rl} 2s_2 + 3s_3 =& 94\cr s_2 + s_3 =& 36\cr \end{array} \] So $s_2=14$ and $s_3=22$. \noindent {\bf Case 3.1:} There is a 2-share $x\le \ob{234}$. $M(x) \ge \ob{470}-\ob{234}=\ob{236}$ so $B(M(x)) \le 1-\ob{236}=\ob{124}$ \noindent {\bf Case 3.2:} There is a 3-share $x\ge \ob{222}$. $B(M_S(x)) \le 1-\frac{\ob{470}-\ob{222}}{2} = \ob{124}$. \noindent {\bf Case 3.3:} There is a 2-share $x \ge \ob{236}$. $B(x) \le 1-\ob{236}=\ob{124}$ \noindent {\bf Case 3.4:} There is a 3-share $x \le \ob{124}$. This one is self-explanatory. \noindent {\bf Case 3.5:} All 3-shares are in $(\ob{124},\ob{222})$ and all 2-shares are in $(\ob{234},\ob{236})$. The following picture captures what we know so far. \[ \begin{array}{ccccccc} ( &---& )[ &---& ]( &---& ) \cr \ob{124} &\hbox{3-shs}&\ob{222}&\hbox{No shs}& \ob{234}&\hbox{2-shs}& \ob{236}\cr \end{array} \] Since there are no shares in $[\ob{222},\ob{234}]$, there are no shares in $B([\ob{222},\ob{234}])=[\ob{126},\ob{138}]$ The following picture captures what we know so far. \[ \begin{array}{ccccccccccc} ( &--- &)[ &--- &]( &--- &)[&--- &]( &--- & ) \cr \ob{124}&\hbox{S3-shs}&\ob{126}&\hbox{No shs}&\ob{138}&\hbox{L3-shs}&\ob{222}&\hbox{No shs}&\ob{234}& \hbox{2-shs} &\ob{236}\cr \end{array} \] S3-shs stands for {\it short 3-shares} and L3-shs stands for {\it large 3-shares}. There are $2s_2=28$ 2-shares so there are 28 S3-shares ($B$ is a bijection between 2-shares and S3-shares). Since there are $3s_3=66$ 3-shares total that leaves 38 S3 shares. Since the midpoint of L3-shs is $\frac{360}{2}$, the Buddy function is a bijection from $(\ob{138},\ob{180})$ to $(\ob{180},\ob{222})$, Hence these two intervals have the same number of shares. Since the midpoint of 2-shs is $\frac{470}{2}$, the Match function is a bijection from $(\ob{234},\ob{235})$ to $(\ob{235},\ob{236})$. Hence these two intervals have the same number of shares. Applying the Buddy function to both these intervals we obtain that $(\ob{124},\ob{125})$ and $(\ob{125},\ob{126})$ have the same number of shares. In the scenarios above there are an even number of shares of size the midpoint. We arbitrarily assign half to the left and half to the right. We define the following intervals. \begin{definition}~ \begin{enumerate} \item $I_1=(\ob{124},\ob{125})$ \item $I_2=(\ob{125},\ob{126})$ ($|I_1|=|I_2|$, $|I_1\cup I_2|=28$) \item $I_3=(\ob{138},\ob{180})$ \item $I_4=(\ob{180},\ob{222})$ ($|I_3|=|I_4|$, $|I_3\cup I_4|=38$) \end{enumerate} \end{definition} Henceforth all of the students considered will be 3-students. We now look at the students in a more detailed way than 2-students and 3-students. \begin{definition}\label{de:EE} Let $1\le i_1\le \cdots \le i_3\le 4$. An $\EE {i_1} {i_2} {i_3}$-student is a student who has, for each $1\le j\le 3$, a share in $I_{i_j}$. For example, an $\EE 1 1 4$-students has two shares in $I_1$ and one share in $I_4$. \end{definition} \noindent {\bf Claim 1: } \begin{enumerate} \item The only possible students are: \begin{enumerate} \item $\EE 1 1 4$ \item $\EE 1 2 4$ \item $\EE 1 3 3$ \item $\EE 1 3 4$ \item $\EE 2 2 4$ \item $\EE 2 3 3$ \item $\EE 2 3 4$ \item $\EE 3 3 3$ \item $\EE 3 3 4$ \end{enumerate} \item There are no shares in $[\ob{208},\ob{218}]$ \item There are no shares in $[\ob{142},\ob{152}]$ (this follows from the prior part and buddying). \end{enumerate} \noindent {\bf Proof of Claim 1:} \noindent 1) We establish that some students are impossible. A $\EE 1 4 4$-student has more than $\ob{124} + 2\times \ob{180} = \ob{484}$ A $\EE 2 2 3$-student has less than $2\times \ob{126} + \ob{180} = \ob{432}$ The result follows from these two statements, though the proof is tedious. \noindent 2) We look at which $I_4$-shares are used A $\EE 1 1 4$ student uses $I_4$-share $> \ob{470}-2\times\ob{125}= \ob{220}$ A $\EE 1 2 4$ student uses $I_4$-shares $> \ob{470}-\ob{125}-\ob{126}= \ob{219}$ A $\EE 1 3 4$ student uses $I_4$-shares $< \ob{470}-\ob{124}-\ob{138}= \ob{208}$ A $\EE 2 2 4$ student uses $I_4$-shares $> \ob{470}-2\times\ob{126}=\ob{218}$ A $\EE 2 3 4$ student uses $I_4$-shares $< \ob{470}-\ob{125}-\ob{138}= \ob{207}$ A $\EE 3 3 4$ student uses $I_4$-shares $< \ob{470}-2\times\ob{138}=\ob{194}$ Hence the only shares in $I_4$ that can be used are those $<\ob{208}$ or $>\ob{218}$. The result follows. \noindent {\bf End of Proof of Claim 1} We redefine the intervals. \begin{definition}~ \begin{enumerate} \item $I_1=(\ob{124},\ob{125})$ \item $I_2=(\ob{125},\ob{126})$ ($|I_1|=|I_2|$), $|I_1\cup I_2|=28$) \item $I_3=(\ob{138},\ob{142})$ \item $I_4=(\ob{152},\ob{180})$ \item $I_5=(\ob{180},\ob{208})$ ($|I_4|=|I_5|$) \item $I_6=(\ob{218},\ob{222})$ ($|I_3|=|I_6|$, $|I_3 \cup I_4 \cup I_5 \cup I_6|=38$) \end{enumerate} \end{definition} By a proof similar to that of Claim 1 we obtain the following: \noindent {\bf Claim 2: } \begin{enumerate} \item The only possible students are: $\EE 1 1 6$, $\EE 1 2 6$, $\EE 1 3 5$, $\EE 1 4 4$, $\EE 1 4 5$, $\EE 2 2 6$, $\EE 2 3 5$, $\EE 2 4 4$, $\EE 2 4 5$, $\EE 3 3 5$, $\EE 3 4 4$, and $\EE 4 4 4$. \item There are no shares in $[\ob{194},\ob{202}]$ \item There are no shares in $[\ob{158},\ob{166}]$ (this follows from the prior part and buddying). \end{enumerate} We define the following intervals. \begin{definition}~ \begin{enumerate} \item $I_1=(\ob{124},\ob{125})$ \item $I_2=(\ob{125},\ob{126})$ ($|I_1|=|I_2|$, $|I_1\cup I_2|=28$) \item $I_3=(\ob{138},\ob{142})$ \item $I_4=(\ob{152},\ob{158})$ \item $I_5=(\ob{166},\ob{180})$ \item $I_6=(\ob{180},\ob{194})$ ($|I_5|=|I_6|$) \item $I_7=(\ob{202},\ob{208})$ ($|I_4|=|I_7|$) \item $I_8=(\ob{218},\ob{222})$ ($|I_3|=|I_8|$, $|I_3\cup \cdots \cup I_8|=38$) \end{enumerate} \end{definition} By a proof similar to that of Claim 1 we obtain: \noindent {\bf Claim 3: } The only possible students are: $\EE 1 1 8$, $\EE 1 2 8$, $\EE 1 3 7$, $\EE 1 4 6$, $\EE 1 5 5$, $\EE 2 2 8$, $\EE 2 3 7$, $\EE 2 4 6$, $\EE 2 5 5$, $\EE 3 3 6$, and $\EE 4 4 4$. Let \begin{enumerate} \item $|\EE 1 1 8|=a$ \item $|\EE 1 2 8|=b$ \item $|\EE 1 3 7|=c$ \item $|\EE 1 4 6|=d$ \item $|\EE 1 5 5|=e$ \item $|\EE 2 2 8|=f$ \item $|\EE 2 3 7|=g$ \item $|\EE 2 4 6|=h$ \item $|\EE 2 5 5|=i$ \item $|\EE 3 3 6|=j$ \item $|\EE 4 4 4|=k$ \end{enumerate} Since $|I_1|=|I_2|$, $2a+b+c+d+e=b+2f+g+h+i$, so $2a+c+d+e=2f+g+h+i$ Since $|I_3|=|I_8|$, $c+g+2j=a+b+f$ Since $|I_4|=|I_7|$, $d+h+3k = c + g$ Since $|I_5|=|I_6|$, $2e + 2i = d + h + j$ Since $|I_1\cup I_2|=28$, $2a+2b+c+d+e+2f+g+h+i=28$ Since there are 22 3-students, $a+b+c+d+e+f+g+h+i+k=22$ From the last two equations we obtain $a+b+f=6$ We combine $I_1$ and $I_2$ into a single interval. This reduces the system to 6 variables, resulting in the equation $$ \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 1 & 1 & 0 & 0 \\ -1& 1 & 0 & 0 & 2 & 0 \\ 0 &-1 & 1 & 0 & 0 & 3 \\ 0 & 0 &-1 & 2 &-1 & 0 \end{bmatrix} \begin{bmatrix} p \\ q \\ r \\ s \\ t \end{bmatrix} = \begin{bmatrix} 22 \\ 28 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$ However, one can check that eliminating the bottom 3 rows requires the top 2 rows to be in the ratio $7:9$. $22:28 \ne 7:9$, so there is no solution. \end{proof} The above proof used that $\ceil{\frac{2m}{s}}=3$ since that is the condition that leads to having 2-shares and 3-shares. This is usually important since it gives us symmetry from matches, not just from buddying; however, in this case we just so happened to not need that symmetry. \section{Finding a Procedure}\label{se:lower} We now describe the program that finds the procedure showing $f(47,36)\ge\ob{124}$. We {\it guess} that all shares are of the form $\ob{x}$ where $124\le x\le 236$. But we can cut down those variables {\it a lot} based on the proof. For example, by modifying the proof slightly, we can deduce that there are no share of size $\ob{127},\ob{128},\ldots,\ob{137}$. This is a key factor in speeding up the program. We can also use the symmetries of where shares can be. For every way to split a muffin we have a variable for how many muffins are split that way, as follows: $(\ob{124},\ob{236})$ is associated to the variables $y_{124,236}$, $(\ob{125},\ob{235})$ is associated with the variable $y_{125,235}$, etc. This variable is the {\it number of muffins} that are split that way. For every way to give muffin shares to a student we have a variable for how many students get that set of shares, as follows: $[\ob{87}, \ob{79}, \ob{69}]$ is associated to the variable $z_{87,79,69}$, $[\ob{118}, \ob{117}]$ is associated to the variables $z_{118,117}$, etc. This variable is the {\it number of students} who get that share-size. For each size we express how many pieces are of that size in two ways. \begin{itemize} \item The number of pieces of that size based on the muffins. For example, the number of pieces of size $\ob{131}$ is $y_{131,256}$. The number of pieces of size $\ob{180}$ is $2\times y_{180,180}$. \item The number of shares of that size based on the students. For example, the number of shares of size $\ob{131}$ is $$z_{124,131,215} + \cdots + z_{130,131,209} + 2z_{131,131,208} + z_{132,131,207} + \cdots + z_{215,131,124}$$ \end{itemize} For each size we get an equation by equating the muffin-based and student-based expressions. We have more equations based on the number of pieces and the number in each interval which falls out of the proof of the upper bound. This leads to a set of linear equations whose solution leads to a procedure. Here is the procedure for $f(47,36) \ge \frac{124}{360}=\frac{117}{180}$ we obtained with this method: \renewcommand{\ob}[1]{\frac{#1}{180}} \begin{enumerate} \item Divide 1 muffin $(\ob{90}, \ob{90})$ \item Divide 2 muffins $(\ob{93}, \ob{87})$ \item Divide 2 muffins $(\ob{101}, \ob{79})$ \item Divide 2 muffins $(\ob{104}, \ob{76})$ \item Divide 6 muffins $(\ob{109}, \ob{71})$ \item Divide 6 muffins $(\ob{111}, \ob{69})$ \item Divide 14 muffins $(\ob{117},\ob{63})$ \item Divide 14 muffins $(\ob{118},\ob{62})$ \item Give 2 students $[\ob{87} \ob{79} \ob{69}]$ \item Give 2 students $[\ob{90} \ob{76} \ob{69}]$ \item Give 2 students $[\ob{93} \ob{71} \ob{71}]$ \item Give 2 students $[\ob{101} \ob{71} \ob{63}]$ \item Give 2 students $[\ob{104} \ob{69} \ob{62}]$ \item Give 6 students $[\ob{109} \ob{63} \ob{63}]$ \item Give 6 students $[\ob{111} \ob{62} \ob{62}]$ \item Give 14 students $[\ob{118} \ob{117}]$ \end{enumerate} The reader should be able to see how to generalize the method outlined above. What is described above is not quite what we have coded up (though we will). The Interval Method (see Section~\ref{se:fc}) is another method to find lower bounds that gives information that can be used to cut down the time to find a procedure. We have coded up a version of what is outlined above with the interval method. We denote the algorithm given above (the one using Buddy-Match) $\VLOWER(m,s,\alpha)$ where one finds a procedure showing $f(m,s)\ge \alpha$, hence verifying that $f(m,s)\ge \alpha$. \section{The Proof that $f(47,36)\le\frac{31}{90}$ Reveals Much More}\label{se:X} The proof that $f(47,36)\le\frac{31}{90}$ can be modified very slightly (just notation) to obtain the following result (which we write in a strange way for later exposition): $$ (\forall k\ge 1) \biggl [f(3\times 11\times k+11+3,33k+3)\le \frac{11k+\frac{7}{5}}{3\times 11\times 3k+3}\biggr ] $$ More generally the following seems to be true empirically: \noindent {\it for all $d$ ($d$ stands for difference and is $m-s$), for all $1\le a\le 3d-1$ ($a,d$ relatively primes), there exists $X$: $$(\forall k\ge 1)\biggl [f(3dk+d+a,3dk+a)\le \frac{dk+X}{3dk+a}\biggr ]$$ } For $d=1$ to 8, for all relevant $a$, we have found $X$. In many concrete cases we have shown that it is also an upper bound. In Section~\ref{se:7} we present the results for the $d=7$ case. Note that we need $k\ge 1$ since if $k=0$ then we no longer have $\ceil{\frac{2m}{s}}=3$. \section{Generating More General Theorems}\label{se:gen} The techniques discussed in Section~\ref{se:X} generate theorems of the form $$(\forall k\ge 1)\biggl [f(3dk+a+d,3dk+a)\le \frac{dk+X}{3dk+a}\biggr ].$$ However, the program can be modified to obtain more general theorems. As noted in Section~\ref{se:X} our program finds interesting values of $X$. That is, the program may find that (say) if $X\le \frac{7}{6}$ then there are no $\EE 1 3 4$-students. What is it about $X\le \frac{7}{6}$ that makes this happen? It may be that (say) $1\le a\le \frac{5d}{7}$ and $a\ne \frac{2d}{3}$ makes this work, and it may be that $X= \max \{\frac{2a}{5},\frac{a+d}{6} \} .$ We have taken the results from the program and, with the help of additional programs and our own ingenuity generated many theorems (we hope to fully automate it soon). These theorems are a great time saver since often the result we want falls out of them directly. We present a sample of such theorems in the Section~\ref{se:sample}. \section{How to find $X$}\label{se:Xlegit} The proof of Theorem~\ref{th:47-36} can be summarizes as follows: The assumption $f(47,36)>\frac{31}{90}$ implies that a certain system of linear equations have a solution where all of the variables are natural numbers between 0 and $s_3=22$. The system had no such solution, hence a contradiction. Imagine that we want an upper bound on $f(47,36)$ but do not know what it is ahead of time. Following the line of reasoning in Section~\ref{se:X} we seek $X$ such that $$f(33+3+11,33+3)\le \frac{11+X}{33+3}.$$ We use a program to simulate the proof of Theorem~\ref{th:47-36} but with $X$ instead of the actual numbers. This program will produce many values of $X$ where something interesting happens, such as a type of student no longer being allowed. The program looks at the (finite) set of interesting values of $X$ and finds the least one that causes the resulting system of linear equations to be unsolvable using natural numbers between 0 and 22. Hence we have a value of $X$. We then use $\VLOWER(47,36,\frac{11+X}{36})$ to find the matching lower bound (if this does not work then the algorithm failed to find $f(m,s)$). For the values $47,36$ it was easy to find the value of $X$. For larger $m,s$ it may be that verifying $f(m,s)\le \alpha$ is faster than finding the $\alpha$. In the next two sections we examine how to speed up finding $X$. We leave it to the reader to generalize the algorithm to any $m,s$ where $\ceil{\frac{2m}{s}}=3$; however, we give the following picture which represents intervals where 3-shares can be. In the picture each nonempty interval has the number of 3-shares in it (though $y$ is not known) and a label such as $I_1$ so we can refer to it. This picture is the result of many buddy-match sequences. \renewcommand{\ob}[1]{\frac{dk+{#1}}{3dk+a}} \[ \begin{array}{cccccccc} (&a+d \ \ \ (I_1)&| & a+d \ \ \ (I_2)&)[ & 0 &] & \cr \ob X& &\ob {\frac{a}{2}} & &\ob {a-X} & &\ob {2X}&\cr \end{array} \] \[ \begin{array}{ccccccccccc} &( & &y \ \ \ (I_3)& &)[ &0& &] & \cr &\ob {2X}& & & &\ob {a+d-3X}& & &\ob {d-a+2X}& \cr \end{array} \] %\[ %\begin{array}{cccccccccccccc} %&( & &2d-a-y \ (I_4) & | & &2d-a-y\ (I_5)& &)[ &0& & ]( &y\ (I_6) &) \cr %&\ob {d-a+2X}& & & \ob{\frac{a+d}{2}} & & & &\ob {2a-2X}& & & \ob{3X}& & \ob{a+d-2X} \cr %\end{array} %\] \[ \begin{array}{ccccccccc} &( & &2d-a-y \ (I_4) & | & &2d-a-y\ (I_5)& &) \cr &\ob {d-a+2X}& & & \ob{\frac{a+d}{2}} & & & &\ob{2a-2X} \cr \end{array} \] \[ \begin{array}{ccccccc} &)[ &0& & ]( &y\ (I_6) &) \cr &\ob {2a-2X}& & & \ob{3X}& & \ob{a+d-2X} \cr \end{array} \] Facts and Caveats: \begin{enumerate} \item $|I_1|=|I_2|$ \item $|I_4|=|I_5|$ \item In the picture it is unclear if the endpoint of $I_1$ is included in $I_1$. We do not include it; however, we take the even number of shares that are at that endpoint and arbitrary assign half to $I_1$ and half to $I_2$. \item There is a similar comment for $I_2$, $I_4$, and $I_5$. \end{enumerate} We denote the version where you do not already have upper bound to check $\BUDMAT(m,s)$ and the version where you do $\BUDMAT(m,s,\alpha)$ where $\alpha$ is the bound. We will avoid using $\BUDMAT(m,s)$ unless $m,s$ are small since it may be slow. \section{How to find $X$ Cheating a Little}\label{se:Xcheatsalittle} Say you want to find $f(213,200)$. Since $\ceil{\frac{2\times 213}{200}}=3$ you could run $\BUDMAT(213,200)$. But the numbers are large! Following the line of reasoning in Section~\ref{se:X} we note that $d=213-200=13$ and generalize the problem to finding an $X$ such that $$f(39k+5+13,39k+5)\le \frac{13k+X}{39k+5}.$$ Lets look at the $k=1$ case: $f(57,44)$. Since $\ceil{\frac{2\times 57}{44}}=3$ you could run $\BUDMAT(57,44)$. But the numbers are small! Oh, thats a good thing! Lets say the answer is $\alpha$. Run $\VLOWER(57,44,\alpha)$ to verify that its a lower bound. If it is then solve $\alpha = \frac{13+X}{39+5}$ to find $X$. The proof you did for $f(57,44)\le \frac{13+X}{39+5}$ can be modified to show $(\forall k\ge 1)[f(39k+5+13,39k+5)\le \frac{13k+X}{39k+5}]$. In particular $f(213,200)\le \frac{13\times 5+X}{39\times 5+5}=\beta$. Run $\VLOWER(213,300,\beta)$ to verify the lower bound (if this does not work then the algorithm failed to find $f(57,44)$). This is cheating a little since we don't really know that the such an $X$ exists. But it has so far. And we do verify in the end. We leave it to the reader to generalize this procedure. We denote this algorithm $\CHEATALITTLE(m,s)$. \section{How to find $X$ Cheating a Lot}\label{se:Xcheatsalot} Say you want to find $f(1717,1650)$. Since $\ceil{\frac{2\times 1717}{1650}}=3$ you could run $\BUDMAT(1717,1650)$. But the numbers are really large! Following the line of reasoning in Section~\ref{se:X} we note that $d=1717-1650=67$ and generalize the problem to finding an $X$ such that $$f(201k+42+67,201k+42)\le \frac{67k+X}{201k+42}.$$ Lets look at the $k=1$ case: $f(310,243)$. These numbers are still big! Lets look at the $k=0$ case: $f(109,42)$. These numbers are small! Since $\ceil{\frac{2\times 109}{42}}\ge 4$ you cannot run $\BUDMAT(109,42))$. But the situation is worse than that. Even if we bound $f(109,42)$ the proof will not use $\BUDMAT$ and hence cannot be modified to get an upper bound for $f(201k+42+67,201k+42)$. In fact, the answer for $f(109,42)$ should have no bearing on our problem. Except for one thing. Empirically it does. In all cases that we looked at the $X$ obtained from knowing an upper bound on the $k=0$ case of $f(3dk+a+d,3dk+a)$ was the correct $X$ for $k\ge 1$. We proceed as if this is always true. We cannot use $\BUDMAT(109,42)$; however, there are other techniques that to find an upper bound on $f(m,s)$. They summarized in Section~\ref{se:fc}. Use them. Lets say the answer is $\alpha$. Run $\VLOWER(109,42,\alpha)$ to verify that its a lower bound. If it is then solve $\alpha = \frac{X}{42}$ to find $X$. The proof you did for $f(109,42)\le \frac{X}{42}$ {\it cannot} be modified to show $(\forall k\ge 1)[f(201k+42+67,201k+42)\le \frac{67k+X}{201+42}]$. But you have a very good conjecture. Run $\BUDMAT(109,42,\frac{67+X}{201+42})$. If it returns YES and a proof then modify the proof to obtain $(\forall k\ge 1)[f(201k+42+67,201k+42)\le \frac{67k+X}{201+42}]$ (if this does not work then the algorithm failed to find $f(1717,1650)$). In particular $f(1717,1658)\le \frac{67\times 5+X}{201\times 5+5}=\beta$. Run $\VLOWER(1717,1658,\beta)$ to verify the lower bound (if this does not work then the algorithm failed to find $f(1717,1650)$). This is cheating a lot since we don't really know that the $k=0$ case has any bearing on the $k\ge 1$ case. But it has so far, and we verify in the end. We leave it to the reader to generalize this procedure. We denote this algorithm $\CHEATALOT(m,s)$. \section{A General Algorithm}\label{se:finalalg} We present an algorithm that we conjecture always finds $f(m,s)$ and operates in polynomial time. The reader should read Section~\ref{se:fc} since we will be using $\FC$, $\INT$, and $\BUD$ which are explained there. They are other methods to find or verify upper bounds on $f(m,s)$. \begin{enumerate} \item Input$(m,s$). \item If $m=s$ output 1. If $gcd(m,s)=d\ge 1$ then call the algorithm recursively with $f(m/d,s/d)$. If $s=2$ then output $\frac{1}{2}$. If $m 0 \implies \y i j <1 \implies \y i j = 0 \implies \x i j + \y i j = \x i j$. \end{itemize} \item Add the constraint $\x i j + \y i j \ge \frac{1}{s}$. Note that \begin{itemize} \item $\x i j =0 \implies \y i j \ge \frac{1}{s} \implies \y i j =1 \implies \x i j + \y i j = 1$ \item $\x i j > 0 \implies \x i j \ge \frac{1}{s}$ (since we know all non-zero pieces are $\ge \frac{1}{s}$) $\implies$ $\x i j + \y i j \ge \frac{1}{s}$, so the constraint imposes no condition on $\y i j$. \end{itemize} \item Replace the constraint $z\le \x i j$ with $z\le \x i j + \y i j$. \end{enumerate} If $\x i j=0$ then the constraint $$z\le \x i j + \y i j = 1$$ is always met and hence is (as it should be) irrelevant. If $\x i j>0$ then the constraint $$z\le \x i j + \y i j = \x i j$$ is the constraint we want. Solve the resulting mixed integer program. Since all of the coefficients are rational the answer will be rational. \end{proof} \section{Other Methods}\label{se:fc} We discuss three methods for finding an upper bound on $f(m,s)$. The method from the following theorem is called {\it The Floor Ceiling Method} or just $\FC$-method. Note that it is very fast and gives you the upper bound. \begin{theorem}\label{th:fc}~ Assume that $m,s\in\N$ and $\frac{m}{s}\notin\N$. $$f(m,s)\le \max\biggl\{\frac{1}{3}, \min\biggl \{\frac{m}{s\ceil{2m/s}},1-\frac{m}{s\floor{2m/s}}\biggr \}\biggr \}.$$ \end{theorem} \begin{proof} Assume we have an optimal $(m,s)$ protocol. Since $\frac{m}{s}\notin\N$ we can assume every muffin is cut into at least 2 pieces. \noindent {\bf Case 1:} Some muffin is cut into $u\ge 3$ pieces. Then some piece is $\le\frac{1}{3}$. \noindent {\bf Case 2:} All muffins are cut into 2 pieces. Since there are $2m$ shares and $s$ students both of the following happen: \begin{itemize} \item Some student gets $t \ge \ceil{2m/s}$ shares, so some share is $\le \frac{m}{s\ceil{2m/s}}.$ \item Some student gets $t \le \floor{2m/s}$ shares, so some share $x$ is $\ge \frac{m}{s\floor{2m/s}}$. $B(x))\le 1- \frac{m}{s\floor{2m/s}}.$ \end{itemize} Putting together Cases 1 and 2 yields the theorem. \end{proof} We denote the function from Theorem~\ref{th:fc} $\FC(m,s)$. The other two methods are to long to describe fully here so we just sketch. The {\it Interval Method} is a primitive version of the Buddy-Match method where we do not use symmetry and (since we have shares other than 2-shares and 3-shares) cannot use the Match in Buddy-Match. This method is fast and can be used to derive the answer. We denote the result $\INT(m,s)$. The {\it Buddy Method} is like the Buddy-Match Method only we do not use the Match part since we have shares other than 2-shares and 3-shares. And like the Buddy-Match Method this one is faster if you already have the answer. We denote the version where you do not already an upper bound to check $\BUD(m,s)$ and the version where you do $\BUD(m,s,\alpha)$ where $\alpha$ is the bound. \section{Everything You Ever Wanted to Know About $f(s+7,s)$}\label{se:7} By either cheating a little (Section~\ref{se:Xcheatsalittle}) or cheating a lot (Section~\ref{se:Xcheatsalot}) we have obtained formulas for $f(3dk+a+d,3dk+a)$ for $1\le d\le 50$ and $1\le a\le 3d-1$ ($a,d$ relatively primes). We present the results for $d=7$. Note that for most of the formulas the formula which is supposed to only hold for $k\ge 1$ also holds for $k=0$ (with a different proof). \begin{theorem}~ \begin{enumerate} \item \begin{enumerate} \item $f(8,1)=1$. For all $k\ge 1$, $f(21k+8,21k+1)\le \frac{7k+X}{21k+1}$ where $X=\frac{1}{2}$. \item For all $k\ge 0$, $f(21k+9,21k+2)\le \frac{7k+X}{21k+2}$ where $X=1$. \end{enumerate} \item For all $k\ge 0$, $f(21k+10,21k+3)\le \frac{7k+X}{21k+3}$ where $X=\frac{4}{3}$. \item For all $k\ge 0$, $f(21k+11,21k+4)=\frac{7k+X}{21k+4}$ where $X=\frac{9}{5}$. \item For all $k\ge 0$, $f(21k+12,21k+5)\le \frac{7k+X}{21k+5}$ where $X=2$. \item For all $k\ge 0$, $f(21k+13,21k+6)\le \frac{7k+X}{21k+6}$ where $X=\frac{13}{5}$. \item For all $k\ge 0$, $f(21k+15,21k+8)\le \frac{7k+X}{21k+8}$ where $X=3$. \item For all $k\ge 0$, $f(21k+16,21k+9)\le \frac{7k+X}{21k+9}$ where $X=\frac{11}{3}$. \item For all $k\ge 0$, $f(21k+17,21k+10)\le \frac{7k+X}{21k+10}$ where $X=4$. \item For all $k\ge 0$ $f(21k+18,21k+11)\le \frac{7k+X}{21k+11}$ where $X=\frac{9}{2}$. \item For all $k\ge 0$ $f(21k+19,21k+12)\le \frac{7k+X}{2ak+12}$ where $X=\frac{19}{4}$. \item For all $k\ge 0$ $f(21k+20,21k+13)\le \frac{7k+X}{21k+13}$ where $X=5$. \item For all $k\ge 0$: $f(21k+22,21k+15)= \frac{1}{3}$, \item For all $k\ge 0$: $f(21k+23,21k+16)= \frac{1}{3}$, \item For all $k\ge 0$: $f(21k+24,21k+17)= \frac{1}{3}$, \item For all $k\ge 0$: $f(21k+25,21k+18)= \frac{1}{3}$, \item For all $k\ge 0$: $f(21k+26,21k+19)= \frac{1}{3}$, \item For all $k\ge 0$: $f(21k+27,21k+20)= \frac{1}{3}$. \end{enumerate} \end{theorem} Note that the last few answers were $\frac{1}{3}$ and there is an equality. The $\frac{1}{3}$ follows from Theorem~\ref{th:onethird}. The equality holds since we have proven that, for all $m>s$, $f(m,s)\ge \frac{1}{3}$. \section{A Sample of General Theorems}\label{se:sample} In all cases $a,d$ are relatively prime. \renewcommand{\ob}[1]{\frac{dk+{#1}}{3dk+a}} \begin{theorem}\label{th:onethird} If $a\in \{2d+1,\ldots,3d-1\}$ then $f(3dk+a+d,3dk+a)\le \ob{X}$ where $X=\frac{a}{3}$, so $f(3dk+a+d,3dk+a)\le \frac{1}{3}$. \end{theorem} \begin{theorem}\label{th:easy5} If $a\in \{1,\ldots,3d-1\}$, $a\ne d$, then $f(3dk+a+d,3dk+a)\le \ob{X}$ where $X= \max \{\frac{a}{3},\frac{a+d}{5},\frac{2a-d}{3} \}.$ \end{theorem} \begin{theorem}\label{th:mod6} If $1\le a\le 3d-1$ and $5a \ne 7d$ then $f(3dk+a+d,3dk+a)\le \ob{X}$ where $X= \max\{\frac{a}{3},\frac{a+d}{5},\frac{a+2d}{6},\frac{3a-2d}{4} \}.$ \end{theorem} \begin{theorem}\label{th:bkx} If $1\le a\le \frac{5d}{7}$ and $a\ne \frac{2d}{3}$ then $f(3dk+a+d,3dk+a)\le \ob{X}$ where $X= \max \{\frac{2a}{5},\frac{a+d}{6} \} .$ \end{theorem} \begin{theorem}\label{th:bky} If $\frac{5d}{7} \le a\le d-1$ then $f(3dk+a+d,3dk+a)\le \ob{X}$ where $X= \max \{ \frac{2a}{5}, \frac{3a-d}{4} \}.$ \end{theorem} \begin{theorem}\label{th:ext31} If $\frac{5d}{13} \le a\le \frac{13d}{29}$ and $a \ne \frac{2}{5}d$ then $f(3dk+a+d,3dk+a)\le \ob{X}$ where $X=\max\{\frac{5a-d}{6},\frac{a+d}{8},\frac{3a}{7}\}$. \end{theorem} \section{If $m\ge s$ then $f(m,s) \ge 1/3$}\label{se:onethird} Before showing the general technique we give an example. \noindent {\bf Example: $f(19,17)\ge \frac{1}{3}$}. We express $\frac{19}{17}$ as $\frac{57}{51}$ since other fractions will have a denominator of 51. We initially divide the 19 muffins $(\third 1 , \third 1 , \third 1 )$. There are now 57 pieces $\third 1$-shares. We initially give 11 students 3 $\third 1$-shares and 6 students 4 $\third 1$-shares. (In the proof below $W=3$, $s_W=s_3=11$, and $s_{W+1}=s_4=6$.) A student who gets 3 (4) shares is called a {\it 3-student (4-student)}. We describe a process whereby students give pieces of muffins, called gifts, to other students so that, in the end, all students have $\frac{57}{51}$. Each gift leads to a change in how the muffins are cut in the first place; however, there will never be a muffin of size $<\frac{1}{3}$. Each 4-student has $\frac{4}{3}=\frac{68}{51}$ and hence has to give (perhaps in several increments) $\frac{68}{51}-\frac{57}{51} =\frac{11}{51}$ to get {\it down to } $\frac{57}{51}$. Realize that if a 4-student gives $\frac{11}{51}$ to a 3-student, then the 3-student now has $\frac{51}{51}+\frac{11}{51}=\frac{62}{51}>\frac{57}{51}$. Each 3-student has $\frac{51}{51}$ and hence has to receive $\frac{57}{51}-\frac{51}{51}=\frac{6}{51}$ to get {\it up to} $\frac{57}{51}$. Call the 11 3-students $g_1,\ldots, g_{11}$. Call the 6 4-students $f_1,\ldots,f_6$. We use a notation that we just give an example of: \newcommand{\arrow}[3]{\frac{{#1}}{51}({#2} \rightarrow {#3})} \newcommand{\arrowg}[3]{{#1}({#2} \rightarrow {#3})} {\it $f_1$ gives $x$ to $g_1$ by taking two $\frac{1}{3}$-pieces, combining them, cutting off a piece of size $x$, giving it to $g_1$ while keeping the rest. $g_1$ takes the piece given to him and combines it with a $\frac{1}{3}$ piece. Notice that in terms of pieces we are taking three pieces of size $\third 1$ (2 from $f_1$ and 1 from $g_1$) and turning them into 1 piece of size $\third 2 - x$ and one of size $\third 1 + x$. Hence we can easily rearrange how the muffins are cut.} \centerline{$\arrowg {x} {f_1} {g_1}$ } We need to make sure this procedure never results in a piece that is $<\frac{1}{3}$. In the above example (1) $f_1$ now has a piece of size $\third 2 -x$, hence we need $x\le \third 1$, (2) $g_1$ now has a piece of size $\third 1 +x$, which is clearly $\ge \third 1$. Hence the only restriction is $x\le \frac{1}{3}$. \begin{enumerate} \item $\arrow {11} {f_1} {g_1}$. Now $f_1$ has $\frac{57}{51}$. YEAH. However, $g_1$ has $\frac{62}{51}$. \item $\arrow 5 {g_1} {g_2}$. Now $g_1$ has $\frac{62}{51}-\frac{5}{51}=\frac{57}{51}$. YEAH. However, $g_2$ has $\frac{51}{51}+\frac{5}{51}=\frac{56}{51}$. \item $\arrow 1 {f_2} {g_2}$. Now $g_2$ has $\frac{57}{51}$. YEAH. However, $f_2$ has $\frac{67}{51}$. \item $\arrow {10} {f_2} {g_3}$. Now $f_2$ has $\frac{57}{51}$. YEAH. However, $g_3$ has $\frac{61}{51}$. \item $\arrow 4 {g_3} {g_4}$. Now $g_3$ has $\frac{57}{51}$. YEAH. However, $g_4$ has $\frac{55}{51}$. \item $\arrow 2 {f_3} {g_4}$. Now $g_4$ has $\frac{57}{51}$. YEAH. However, $f_3$ has $\frac{66}{51}$. \item $\arrow 9 {f_3} {g_5}$. Now $f_3$ has $\frac{57}{51}$. YEAH. However, $g_5$ has $\frac{60}{51}$. \item $\arrow 3 {g_5} {g_6}$. Now $g_5$ has $\frac{57}{51}$. YEAH. However, $g_6$ has $\frac{54}{51}$. \item $\arrow 3 {f_4} {g_6}$. Now $g_6$ has $\frac{57}{51}$. YEAH. However, $f_4$ has $\frac{65}{51}$. \item $\arrow 8 {f_4} {g_7}$. Now $f_4$ has $\frac{57}{51}$. YEAH. However, $g_7$ has $\frac{59}{51}$. \item $\arrow 2 {g_7} {g_8}$. Now $g_7$ has $\frac{57}{51}$. YEAH. However, $g_8$ has $\frac{53}{51}$. \item $\arrow 4 {f_5} {g_8}$. Now $g_8$ has $\frac{57}{51}$. YEAH. However, $f_5$ has $\frac{64}{51}$. \item $\arrow 7 {f_5} {g_9}$. Now $f_5$ has $\frac{57}{51}$. YEAH. However, $g_9$ has $\frac{58}{51}$. \item $\arrow 1 {g_9} {g_{10}}$. Now $g_9$ has $\frac{58}{51}$. YEAH. However, $g_{10}$ has $\frac{52}{51}$. \item $\arrow 5 {f_6} {g_{10}}$. Now $g_{10}$ has $\frac{57}{51}$. YEAH. However, $f_6$ has $\frac{63}{51}$. \item $\arrow 6 {f_6} {g_{11}}$. Now $f_6$ has $\frac{57}{51}$. YEAH. However, $g_{11}$ has $\frac{57}{51}$. OH. thats a good thing! \end{enumerate} YEAH- we are done. Note that the first $x$ was $\frac{11}{51}\le \third 1$ and the remaining $x$ were all $\le \frac{11}{51}\le \third 1$. Hence all pieces in the final protocol are $\ge \frac{1}{3}$. \noindent {\bf End of Example} \begin{theorem} For all $m\ge s$, $f(m,s)\ge \third 1$. \end{theorem} \begin{proof} Divide all the muffins into $(\third 1 , \third 1 , \third 1)$. Initially distribute them as evenly as possible among the students. There will be a number $W$ such that some students get $W$ shares and some get $(W+1)$-shares. Let $s_{W}$ ($s_{W+1})$ be the number of students who get $W$ ($W+1$) shares. We do not need the following but are noting it anyway. If $s$ does not divide $3m$ then $W=\frac{3m}{s}$ and $s_W, \swp$ are unique and determined by: \[ \begin{array}{rl} Ws_W + (W+1)\swp &=3m\cr s_W + \swp &=s\cr \end{array} \] (Technically, if $s \mid 3m$ there are two possible values of $W$.) A student who gets $W$ $(W+1$) shares we call a $W$-student ($(W+1)$-student). All $W$-students get $\frac{W}{3}$. All $(W+1)$-students get $\frac{W+1}{3}$. A $W$-student must get $<\mos$: if a $W$-student got $>\mos$ then all students would get $>\mos$ and hence there would be $>s\mos = m$ muffins total. A $(W+1)$-student must get $>\mos$: if a $(W+1)$-student got $<\mos$ then all students would get $<\mos$ and hence there would be $ \mos - \frac{W}{3}$. \item If $s_{W}<\swp$ then $\frac{W+1}{3} - \mos > \mos - \frac{W}{3}$. \end{enumerate} \noindent {\bf Proof of Claim 1:} $$\swp \times \frac{W+1}{3} + s_W\times \frac{W}{3} = m$$ $$ \swp \times \biggl(\mos + \frac{W+1}{3}-\mos\biggr)+s_W\biggl (\mos + \frac{W}{3} - \mos\biggr ) = m. $$ $$ \biggl(\swp+s_W\biggr)\mos+\swp\biggl(\frac{W+1}{3}-\mos\biggr) + s_W\biggl(\frac{W}{3}-\mos\biggr ) = m$$ $$s\times \mos + \swp\biggl (\frac{W+1}{3}-\mos\biggr ) + s_W\biggl (\frac{W}{3}-\mos\biggr ) = m$$ $$\frac{W+1}{3}-\mos = \frac{s_W}{\swp}\biggl (\mos -\frac{W}{3}\biggr)$$ Both parts follow. \noindent {\bf End of Proof of Claim 1} We give the procedure to obtain $f(m,s)\le \third 1$. There are two cases. \noindent {\bf Case 1:} $\swp < s_W$. Hence by Claim 1 $\frac{W+1}{3} - \mos > \mos - \frac{W}{3}$. Call the $s_W$ $W$-students $g_1,\ldots, g_{s_W}$. Call the $\swp$ $(W+1)$-students $f_1,\ldots,f_{\swp}$. \begin{enumerate} \item Let $x=\frac{W+1}{3} - \mos$. Note that $x\le \frac{1}{3}$. Do $\arrowg x {f_1} {g_1}$. Now $f_1$ has $\frac{m}{s}$. YEAH. However, $g_1$ has $\frac{W}{3}+\frac{W+1}{3}-\mos>\mos$. (This is where we use $\swp < s_W$, or more accurately the consequence of that from Claim 1.) \item Let $x=\frac{2W+1}{3} -2\mos$. Do $\arrowg x {g_1} {g_2}$. Now $g_1$ has $\frac{m}{s}$. YEAH. \item If $g_2$ has $>\mos$ then $g_2$ gives enough to $g_3$ so that $g_2$ has $\mos$. Keep up this chain of $g_1,g_2,g_3,\ldots$ until there is a $g_i$ such that $g_i$ end up with $<\mos$ (though more than the $\frac{W}{3}$ that $g_i$ had originally). \item Do $\arrowg x {f_2} {g_i}$ where $x$ is such that $g_i$ will now have $\mos$. \item Do $\arrowg x {f_2}{g_{i+1}}$ where $x$ is such that $f_2$ will now have $\mos$. Repeat the same chain of $g_i$'s as in step 3. \item Repeat the above steps until you are done. \end{enumerate} We need to show that (1) there is never a piece of size $<\third 1$, and (2) the process ends with every student getting $\mos$. \noindent {\bf Claim 2:} The first gift is $\le \third 1$ and no gift is larger. \noindent {\bf Proof of Claim 2:} Let $C=\frac{W+1}{3} - \frac{m}{s}$ which is the size of the first gift. By equation (2) $C\le \third 1$. Assume that all gifts so far have been $\le C$. We analyze the three kinds of gifts and show that in all cases the gift is $\le C$. \begin{itemize} \item $\arrowg x {f_i} {g_j}$ where (1) initially $f_i$ has $>\mos$, $g_j$ has $<\mos$, and (2) after the gift $f_i$ has $\mos$. When this occurs it is $f_i$'s first or second gift giving. (This happens in steps 1 and 5 above, and later as well.) Before the gift $f_i$ has at least $\frac{m}{s}$ but at most $\frac{W+1}{3}$, so this gift has size at most $\frac{W+1}{3} - \mos = C$. \item $\arrowg x {g_i} {g_{i+1}}$ where (1) initially $g_i$ has $>\mos$, $g_j$ has $<\mos$, and (2) after the gift $g_i$ has $\mos$. When this occurs $g_i$ has received a gift once and this is $g_i$'s first time giving. (This happens in steps 2 and in the chain referred to in step 5.) Since $g_i$ just received a gift of size $\le C$ she has $\le \frac{W}{3} + C$. Hence the gift is $\le \frac{W}{3} -\mos + C \le C$. \item $\arrowg x {f_i} {g_j}$ where (1) initially $f_i$ has $>\mos$, $g_j$ has $<\mos$, and (2) after the gift $g_j$ has $\mos$. This will be $f_i$'s first time giving. (This happens in step 4 above.) Before the gift $f_i$ has at least $\frac{W}{3}$ but at most $\frac{m}{s}$, so this gift has size at most $\mos - \frac{W}{3} \le C$ (by Claim 1). \end{itemize} {\bf Claim 3:} If $s_W$ and $\swp$ are relatively prime then the process terminates with all students having $\mos$. \noindent {\bf Proof of Claim 3:} In each step all of the $f_i$ have at least $\frac{m}{s}$. In each step the number of students who have the correct amount of muffin goes up. One may be worried that at some point we will try to do step 4 (for example) of the procedure and there will be no $g_i$ left who need more muffin. But this is not possible because until the process terminates the $f$'s always have more muffin than they need, so there is always a $g$ with insufficient muffin. One may also be worried that eventually we will get all of the $f$'s to have $\frac{m}{s}$, but the $g$'s will not all have $\frac{m}{s}$. This is not possible either, because whenever we only make gifts from $f$ to $g$ when there is no $g$ with more than $\frac{m}{s}$. Finally, if $\sw$ and $\swp$ are not relatively prime, it is possible that the procedure will terminate early because in step 5 the size of the donation $x$ is 0. If this occurred it would mean that there is some subset of $F$ $f$'s and $G$ $g$'s each of which having exactly $\frac{m}{s}$, who only made donations amongst themselves. But then $\frac{F}{G} = \frac{\swp}{\sw}$, a contradiction. \noindent {\bf End of Proof of Claim 3} \noindent {\bf Case 2:} $s_W < \swp$. This is similar to Case 1 except that instead of $f_1$ giving $g_1$ so that $f_1$ has $\mos$, $f_1$ gives to $g_1$ so that $g_1$ has $\mos$. Hence we have a chain of $f_i$'s instead of a chain of $g_i$'s. \end{proof} %\bibliography{bibfile} \begin{thebibliography}{1} \bibitem{muffin} Alan Frank. \newblock The muffin problem, 2013. \newblock Described to Jeremy Copeland and in the New York Times Numberplay Online Blog \url{wordplay.blogs.nytimes.com/2013/08/19/cake}. \end{thebibliography} \end{document}