\makeatletter\let\ifGm@compatii\relax\makeatother \documentclass[red]{beamer} %\usepackage{beamerthemesplit} \usepackage{url} \usepackage{listings} \usepackage{comment} \usepackage{mathdots} \usepackage{bm} \DeclareMathOperator{\FC}{FC} \DeclareMathOperator{\INT}{INT} \DeclareMathOperator{\GAPS}{GAPS} \DeclareMathOperator{\MATRIX}{MATRIX} % This % ANY LATEX paper. Typically I'll use this file and some other file in the % directory of the paper, this one for general math things, that one for % things specific to that paper. % % font's used and general paper things. \newcommand{\x}[2]{x_{ #1 #2}} \newcommand{\y}[2]{y_{ #1 #2}} \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \xdefinecolor{darkgreen}{rgb}{0, 0.50, 0} \newcommand{\bigfloor}[1]{{\biggl\lfloor {#1} \biggr\rfloor}} \newcommand{\bigceiling}[1]{{\biggl\lceil {#1} \biggr\rceil}} \newcommand{\isred}[1]{{\color{red} {\bf #1}}} \newcommand{\isblue}[1]{{\color{blue}{\bf #1}}} \newcommand{\isgreen}[1]{{\color{green} {#1}}} \newcommand{\isdarkgreen}[1]{{\color{darkgreen} {#1}}} \newcommand{\isorange}[1]{{\color{orange} {#1}}} \newcommand{\isdef}[1]{{\color{blue} {#1}}} \newcommand{\iscase}[1]{{\color{blue} {#1}}} \newcommand{\isnote}[1]{{\color{blue} {#1}}} \newcommand{\isexample}[1]{{\color{orange} {#1}}} \newcommand{\R}{\color{red} R} \newcommand{\B}{\color{blue} B} \newcommand{\G}{\color{darkgreen} G} \newcommand{\Y}{\color{purple} P} \newcommand{\Q}{\color{orange} O} \newcommand{\itr}[1]{\color{red} {#1}} \newcommand{\itb}[1]{\color{blue} {#1}} \newcommand{\Z}{{\sf Z}} \newcommand{\nat}{{\sf N}} \newcommand{\rat}{{\sf Q}} \newcommand{\real}{{\mathbb R}} \newcommand{\sphere}{{\mathbb S}} \newcommand{\complex}{{\sf C}} \newcommand{\Rpos}{{\sf R}^+} \newcommand{\ie}{\hbox{ i.e. }} \newcommand{\eg}{\hbox{ e.g. }} \newcommand{\Kobler}{K\"obler} \newcommand{\Schoning}{Sch\"oning} \newcommand{\Toran}{Tor\'an} \newcommand{\Balcazar}{Balc{\'a}zar} \newcommand{\Diaz}{D\'{\i}az} \newcommand{\Gabarro}{Gabarr{\'o}} \newcommand{\Laszlo}{L{\'a}szl{\'o}} \newcommand{\Erdos}{Erd\"os } \newcommand{\Erdosns}{Erd\"os} \newcommand{\Sarkozy}{S{\'a}rk{\"o}zy } \newcommand{\Sarkozyns}{S{\'a}rk{\"o}zy} \newcommand{\Szekely}{Sz{\'e}kely } \newcommand{\Szekelyns}{Sz{\'e}kely} \newcommand{\Szemeredi}{Szemer{\'e}di } \newcommand{\Szemeredins}{Szemer{\'e}di} \newcommand{\Holder}{H{\"o}lder } \newcommand{\Holderns}{H{\"o}lder} \newcommand{\Chv}{Chv{\'a}tal } \newcommand{\Chvns}{Chv{\'a}tal} \begin{document} \setbeamercolor{alerted_text}{fg=cyan} \xdefinecolor{purplish}{cmyk}{0.75,0.75, 0, 0} \xdefinecolor{purple}{cmyk}{0.75,0.75, 0, 0} \colorlet{newred}{red!60!black} \title{\bf The Muffin Problem} \author{ {William Gasarch - University of MD}\\ {Erik Metz - University of MD}\\ {Jacob Prinz-University of MD}\\ {Daniel Smolyak- University of MD}\\ } \date{} \maketitle \begin{frame}\frametitle{\bf How it Began} \centerline{\isblue{A Recreational Math Conference}} \centerline{\isblue{(Gathering for Gardner)}} \centerline{\isblue{May 2016}} I found a pamphlet: \centerline{\isblue{The Julia Robinson Mathematics Festival:}} \centerline{\isblue{A Sample of Mathematical Puzzles}} \centerline{\isred{Compiled by Nancy Blachman}} which had this problem, proposed by \isred{Alan Frank}: \bigskip \noindent \isblue{\it How can you divide and distribute 5 muffins to 3 students so that every student gets $\bm{\frac{5}{3}}$ where nobody gets a tiny sliver?} \bigskip \includegraphics[scale=.3]{muffinw.eps} \end{frame} \begin{frame}\frametitle{\bf 5 Muffins, 3 Students, Proc by Picture} \[ \begin{tabular}{|lll|} \hline Person & Color & What they Get \cr \hline & & \cr Alice & \isred{RED} & $1 +\frac{2}{3}=\frac{5}{3}$ \cr & & \cr Bob & \isblue{BLUE} & $1 +\frac{2}{3}=\frac{5}{3}$ \cr & & \cr Carol & \isdarkgreen{GREEN} & $1 +\frac{1}{3}+\frac{1}{3}=\frac{5}{3}$ \cr & & \cr \hline \end{tabular} \] \centerline{\bf Smallest Piece: $\frac{1}{3}$} \medskip \includegraphics[scale=.3]{muffin35a.eps} \smallskip \end{frame} \begin{frame}\frametitle{\bf Can We Do Better?} \vspace{-80pt} The smallest piece in the above solution is $\frac{1}{3}$. \isblue{Is there a procedure with a larger smallest piece?} \isred{Work on it with your neighbor} \end{frame} \begin{frame}\frametitle{\bf 5 Muffins, 3 People--Proc by Picture} \isred{YES WE CAN!} \[ \begin{tabular}{|lll|} \hline Person & Color & What they Get \cr \hline & & \cr Alice & \isred{RED} & $\frac{6}{12}+\frac{7}{12}+\frac{7}{12}$ \cr & & \cr Bob & \isblue{BLUE} & $\frac{6}{12}+\frac{7}{12}+\frac{7}{12}$ \cr & & \cr Carol & \isdarkgreen{GREEN} & $\frac{5}{12}+\frac{5}{12}+\frac{5}{12} +\frac{5}{12}$\cr & & \cr \hline \end{tabular} \] \centerline{\bf Smallest Piece: $\frac{5}{12}$} \medskip \includegraphics[scale=.3]{muffin35c2.eps} \end{frame} \begin{frame}\frametitle{\bf Can We Do Better?} \vspace{-60pt} The smallest piece in the above solution is $\frac{5}{12}$. \isblue{Is there a procedure with a larger smallest piece?} \isred{Work on it with your neighbor} \end{frame} \begin{frame}\frametitle{\bf 5 Muffins, 3 People--Can't Do Better Than \boldmath{$\frac{5}{12}$}} %\vspace{-50pt} \isred{NO WE CAN'T!} There is a procedure for 5 muffins,3 students where each student gets $\frac{5}{3}$ muffins, smallest piece $N$. We want $N\le \frac{5}{12}$. \bigskip \isblue{\bf Case 0:} Some muffin is uncut. Cut it $(\frac{1}{2},\frac{1}{2})$ and give both $\frac{1}{2}$-sized pieces to whoever got the uncut muffin. (Note $\frac{1}{2}>\frac{5}{12}$.) Reduces to other cases. (\isred{Henceforth:} All muffins cut into $\bm{\ge 2}$ pieces.) \pause \bigskip \isblue{\bf Case 1:} Some muffin is cut into $\ge 3$ pieces. Then $N\le\frac{1}{3}<\frac{5}{12}$. (\isred{Henceforth:} All muffins cut into 2 pieces.) \pause \bigskip \isblue{\bf Case 2:} All muffins are cut into 2 pieces. 10 pieces, 3 students: \isred{Someone} gets $\ge 4$ pieces. He has some piece $$ \le \frac{5}{3}\times\frac{1}{4}=\frac{5}{12}\hbox{\ \ \ \ \ Great to see } \frac{5}{12} $$ \end{frame} \begin{frame}\frametitle{\bf What Else Was in the Pamphlet?} The pamphlet also had asked about \begin{enumerate} \item 4 muffins, 7 students. \item 12 muffins, 11 students. \item a few others \end{enumerate} \pause This seemed like a nice exercise and it was. \bigskip \pause There can't be much more to this. \end{frame} \begin{frame}\frametitle{\bf If there is not much more to this then how come} \url{https://www.amazon.com/Mathematical-Muffin-Morsels-Problem-Mathematics/dp/9811215170} \bigskip \pause The following happened: \begin{itemize} \pause \item Find a technique that solves many problems (e.g., Floor-Ceiling). \pause \item Come across a problem where the techniques do not work. \pause \item Find a new technique \isred{which was interesting}. \pause \item Lather, Rinse, Repeat. \end{itemize} \end{frame} \begin{frame}\frametitle{\bf General Problem} \vspace{-20pt} \isblue{$\bm{f(m,s)}$} be the smallest piece in the best procedure (best in that the smallest piece is maximized) to divide $m$ muffins among $s$ students so that everyone gets $\frac{m}{s}$. \bigskip We have shown $f(5,3)=\frac{5}{12}$ here. \bigskip We have shown $f(m,s)$ exists, is rational, and is computable using a \isblue{Mixed Int Program}. \pause This was a case of a Theorem in \isred{Applied Math} being used to prove a Theorem in \isred{Pure Math}. \end{frame} \begin{frame}\frametitle{\bf Amazing Results!/Amazing Theorems!} \vspace{-30pt} \begin{enumerate} \item $f(43,33)=\frac{91}{264}$. \item $f(52,11)=\frac{83}{176}$. \item $f(35,13)=\frac{64}{143}$. \end{enumerate} \bigskip \pause \isred{All done by hand, no use of a computer} \pause \isred{by Co-author Erik Metz is a} \isblue{muffin savant} ! \bigskip \pause Have \isred{General Theorems} from which \isred{upper bounds} follow. Have \isred{General Procedures} from which \isred{lower bounds} follow. \end{frame} \begin{frame}\frametitle{\bf Conventions} \isred{Duality Theorem:} $f(m,s) = \frac{m}{s} f(s,m)$. \pause \isblue{We know and use the following:} \begin{enumerate} \item \pause By Duality Theorem can assume $m>s$ \item \pause By REASONS we can assume $m,s$ are relatively prime. \item \pause All muffins are cut in $\ge 2$ pcs. Replace uncut muff with 2 $\frac{1}{2}$'s %\item %\pause %If assuming $f(m,s)>\alpha >\frac{1}{3}$, assume all muffin in $\le 2$ pcs. %\item %\pause %$f(m,s)>\alpha >\frac{1}{3}$, so exactly 2 pcs, is common case. \end{enumerate} \end{frame} \begin{frame}\frametitle{\bf 7 Muffins, 3 Students} Work on $f(7,3)$ in groups. 7 Muffins, 3 Students. Get upper and lower bounds that match! \end{frame} \begin{frame}\frametitle{\bf 7 Muffins, 3 Students: How to think about it} We first look at LIMITS on what we can expect. \begin{enumerate} \pause \item If a muffin is uncut, can cut it in two. \pause \item If a muffin is cut in $\ge 3$ pieces then some piece $\le \frac{1}{3}$. Unlikely. \pause \item 7 muffins, each one cut in two 2 pieces, so 14 pieces total. \pause \item 3 students, so some student gets $\ge \ceil{\frac{14}{3}}=5$ pieces. \pause \item That student must get a piece $\le \frac{7}{3}\times\frac{1}{5}=\frac{7}{15}$. \pause \item Great! We know $f(7,3) \le \frac{7}{15}$. \pause \item Can we show a protocol that gives $f(7,3) \ge \frac{7}{15}$. \pause \item We tried. We failed. Darn :-( \end{enumerate} \pause Now what? \end{frame} \begin{frame}\frametitle{\bf 7 Muffins, 3 Students: How to think about it again} We first look at LIMITS on what we can expect. \begin{enumerate} \pause \item If a muffin is uncut, can cut it in two. \pause \item If a muffin is cut in $\ge 3$ pieces then some piece $\le \frac{1}{3}$. Unlikely. \pause \item 7 muffins, each one cut in two 2 pieces, so 14 pieces total. \pause \item 3 students, so some student gets $\le \floor{\frac{14}{3}}=4$ pieces. \pause \item That student must get a piece $\ge \frac{7}{3}\times\frac{1}{4}=\frac{7}{12}$. \pause \item That piece came from a muffin. Other piece is $\le 1-\frac{7}{12}=\frac{5}{12}$. \pause \item Great! We know $f(7,3) \le \frac{5}{12}$. \pause \item Can we show a protocol that gives $f(7,3) \ge \frac{5}{12}$? \end{enumerate} \end{frame} \begin{frame}\frametitle{\bf 7 Muffins, 3 Students: How to think about protocol} Want $f(7,3)\ge \frac{5}{12}$. \pause Will be cutting some muffins $(\frac{5}{12},\frac{7}{12})$. \pause Can also cut some muffins $(\frac{6}{12},\frac{6}{12})$. \pause Need to know what combos of $\frac{5}{12},\frac{6}{12},\frac{7}{12}$ add to $\frac{7}{3}=\frac{28}{12}$. \pause Need to know what combos of $5,6,7$ add to 28. $7+7+7+7=28$ $5+5+6+6+6=28$ \begin{enumerate} \pause \item Cut 4 muffins $(\frac{5}{12},\frac{7}{12})$. \pause \item Cut 3 muffins $(\frac{6}{12},\frac{6}{12})$. \pause \item Give 1 student 4 pieces of size $\frac{7}{12}$. \pause \item Give 2 students 2 pieces of size $\frac{5}{12}$ and 3 pieces of size $\frac{6}{12}$. \end{enumerate} \end{frame} \begin{frame}\frametitle{\bf 8 Muffins, 3 Students} Work on $f(8,3)$ in groups. 8 Muffins, 3 Students. Get upper and lower bounds that match! \end{frame} \begin{frame}\frametitle{\bf 8 Muffins, 3 Students: How to think about it} We first look at LIMITS on what we can expect. \begin{enumerate} \pause \item If a muffin is uncut, can cut it in two. \pause \item If a muffin is cut in $\ge 3$ pieces then some piece $\le \frac{1}{3}$. Unlikely that thats a good idea. \pause \item 8 muffins, each one cut in two 2 pieces, so 16 pieces total. \pause \item 3 students, so some student gets $\ge \ceil{\frac{16}{3}}=6$ pieces. That student must get a piece $\le \frac{8}{3}\times\frac{1}{6}=\frac{4}{9}$. \pause \item 3 students, so some student gets $\le \floor{\frac{16}{3}}=5$ pieces. That student must get a piece $\ge \frac{8}{3}\times\frac{1}{5}=\frac{8}{15}$. So there is some piece of size $\le 1-\frac{8}{15}=\frac{7}{15}$. \pause \item Great! We know $f(8,3) \le \min\{\frac{4}{9},\frac{7}{15}\}=\frac{4}{9}$. \pause \item Can we show a protocol that gives $f(8,3) \ge \frac{4}{9}$? \end{enumerate} \end{frame} \begin{frame}\frametitle{\bf 8 Muffins, 3 Students: How to think about protocol} Want $f(8,3)\ge \frac{4}{9}$. \pause Will be cutting some muffins $(\frac{4}{9},\frac{5}{9})$. \pause $\frac{1}{2}$ was helpful last time so lets also include $\frac{4.5}{9}$. Need to know what combos of $\frac{4}{9},\frac{4.5}{9},\frac{5}{9}$ add to $\frac{8}{3}=\frac{24}{9}$. \pause Need to know what combos of $4,4.5,5$ add to 24 $4+4+4+4+4+4=24$ $4.5+4.5+5+5+5=24$ \begin{enumerate} \pause \item Cut 6 muffins $(\frac{4}{9},\frac{5}{9})$. \item Cut 2 muffins $(\frac{4.5}{9},\frac{4.5}{9})$. \item Give 1 student six $\frac{4}{9}$ pieces. \item Give 2 students two $\frac{4.5}{9}$ pieces and four $\frac{5}{9}$ pieces. \end{enumerate} \end{frame} \begin{frame}\frametitle{\bf FC Thm Generalizes $\bm{f(5,3)\le \frac{5}{12}}$} \vspace{-20pt} %Generalize proof that $f(5,3)\le \frac{5}{12}$. $$f(m,s)\le \FC(m,s)=\max\biggl \{\frac{1}{3},\min\biggl \{\frac{m}{s\ceil{2m/s}},1-\frac{m}{s\floor{2m/s}}\biggr \} \biggr \}.$$ \pause \bigskip \isblue{\bf Case 0:} Some muffin is uncut. Cut it $(\frac{1}{2},\frac{1}{2})$ and give both halves to whoever got the uncut muffin, so reduces to other cases. \pause \bigskip \isblue{\bf Case 1:} Some muffin is cut into $\ge 3$ pieces. Some piece \isred{$\bm{\le \frac{1}{3}}$.} \pause \bigskip \isblue {\bf Case 2:} Every muffin is cut into 2 pieces, so $2m$ pieces. \pause \bigskip \isred{Someone} gets $\ge \ceil{\frac{2m}{s}}$ pieces. $\exists$ piece $\le \frac{m}{s}\times\frac{1}{\ceil{2m/s}}=\isred{\bm{\frac{m}{s\ceil{2m/s}}}}$. \pause \bigskip \isred{Someone} gets $\le \floor{\frac{2m}{s}}$ pieces. $\exists$ piece $\ge \frac{m}{s}\frac{1}{\floor{2m/s}}= \frac{m}{s\floor{2m/s}}.$ \pause \medskip The other piece from that muffin is of size \isred{$\bm{\le 1-\frac{m}{s\floor{2m/s}}}$.} \end{frame} \begin{frame}\frametitle{\bf THREE Students} \vspace{-30pt} \isblue{CLEVERNESS, COMP PROGS} for the procedure. \medskip \isblue{FC Theorem} for optimality. \bigskip \pause $f(1,3)=\frac{1}{3}$ \bigskip \pause $f(3k,3)=1$. \bigskip \pause $f(3k+1,3)=\frac{3k-1}{6k}$, $k\ge 1$. \bigskip \pause $f(3k+2,3)=\frac{3k+2}{6k+6}$. \bigskip \pause \isred{Note:} A Mod 3 Pattern. \isred{Theorem:} For all $m\ge 3$, $f(m,3)=\FC(m,3)$. \end{frame} \begin{frame}\frametitle{\bf FOUR Students} \vspace{-10pt} \isblue{CLEVERNESS, COMP PROGS} for procedures. \medskip \isblue{FC Theorem} for optimality. \bigskip \pause $f(4k,4)=1$ (easy) \bigskip \pause $f(1,4)=\frac{1}{4}$ (easy) \bigskip \pause $f(4k+1,4)=\frac{4k-1}{8k}$, $k\ge 1$. \bigskip \pause $f(4k+2,4)=\frac{1}{2}$. \bigskip \pause $f(4k+3,4)=\frac{4k+1}{8k+4}$. \bigskip \isred{Note:} A Mod 4 Pattern. \isred{Theorem:} For all $m\ge 4$, $f(m,4)=\FC(m,4)$. \pause \isred{FC-Conjecture:} For all $m,s$ with $m\ge s$, $f(m,s)=\FC(m,s)$. \end{frame} \begin{frame}\frametitle{\bf FIVE Students} \vspace{-10pt} \isblue{CLEVERNESS, COMP PROGS} for procedures. \medskip \isblue{FC Theorem} for optimality. \bigskip \pause For $k\ge 1$, $f(5k,5)=1$. \bigskip \pause For $k=1$ and $k\ge 3$, $f(5k+1,5) = \frac{5k+1}{10k+5}$. $f(11,5)$? \bigskip \pause For $k\ge 2$, $f(5k+2,5) = \frac{5k-2}{10k}$. $f(7,5)=\FC(7,5)=\frac{1}{3}$ \bigskip \pause For $k\ge 1$, $f(5k+3,5) = \frac{5k+3}{10k+10}$ \bigskip \pause For $k\ge 1$, $f(5k+4,5)= \frac{5k+1}{10k+5}$ \isred{Note:} A Mod 5 Pattern. \pause \isred{Theorem:} For all $m\ge 5$ \isblue{except m=11}, $f(m,5)=\FC(m,5)$. \end{frame} \begin{frame}\frametitle{\bf What About FIVE students, ELEVEN muffins?} $$f(11,5)\le \max \bigg \{ \frac{1}{3},\min \biggl \{\frac{11}{5\ceil{22/5}},1-\frac{11}{5\floor{22/5}}\biggr \} \biggr \} =\frac{11}{25}.$$ \pause We tried to find a protocol to divide 11 muffins for 5 people, each gets $\frac{11}{5}$, and smallest piece is size $\frac{11}{25}=0.44$. \pause We found a protocol with smallest piece $\frac{13}{30}=0.4333\ldots$. \begin{enumerate} \item Divide 1 muffin $(\frac{15}{30},\frac{15}{30})$. \item Divide 2 muffins $(\frac{14}{30},\frac{16}{30})$. \item Divide 8 muffins $(\frac{13}{30},\frac{17}{30})$. \item Give 2 students $[ \frac{13}{30}, \frac{13}{30}, \frac{13}{30}, \frac{13}{30}, \frac{14}{30}]$ \item Give 1 students $[ \frac{16}{30}, \frac{16}{30}, \frac{17}{30}, \frac{17}{30}]$ \item Give 2 students $[ \frac{15}{30}, \frac{17}{30}, \frac{17}{30}, \frac{17}{30}]$ \end{enumerate} \end{frame} \begin{frame}\frametitle{\bf So Now What?} We have: $$\frac{13}{30} \le f(11,5) \le \frac{11}{25}\hbox{\ \ \ \ Diff= $0.006666\ldots$}$$ \pause Options: \begin{enumerate} \item $f(11,5)=\frac{11}{25}$. Need to find procedure. \item $f(11,5)=\frac{13}{30}$. Need to find new technique for upper bounds. \item $f(11,5)$ in between. Need to find both. \item $f(11,5)$ unknown to science! \end{enumerate} \isblue{Vote} \pause $\isred{\hbox{WE SHOW: }\bm{f(11,5)=\frac{13}{30}}}$. \isred{Exciting} new technique! \end{frame} \begin{frame}\frametitle{\bf Terminology: Buddy} Assume that in some protocol every muffin is cut into two pieces. \bigskip Let $x$ be a piece from muffin $M$. The {\it other piece} from muffin $M$ is the {\it buddy of $x$}. \bigskip Note that the buddy of $x$ is of size $$1-x.$$ \end{frame} \begin{frame}\frametitle{\bf \boldmath{$f(11,5) = \frac{13}{30}$}, Easy Case Based on Muffins} \vspace{-30pt} There is a procedure for 11 muffins, 5 students where each student gets $\frac{11}{5}$ muffins, smallest piece $N$. We want $N\le \frac{13}{30}$. \bigskip \isblue{\bf Case 0:} Some muffin is uncut. Cut it $(\frac{1}{2},\frac{1}{2})$ and give both halves to whoever got the uncut muffin. Reduces to other cases. \pause \bigskip \isblue{\bf Case 1:} Some muffin is cut into $\ge 3$ pieces. $N\le \frac{1}{3}<\frac{13}{30}$. \medskip (\isred{Negation of Case 0 and Case 1:} All muffins cut into 2 pieces.) \end{frame} \begin{frame}\frametitle{\bf \boldmath{$f(11,5) = \frac{13}{30}$}, Easy Case Based on Students} \vspace{-20pt} \isblue{\bf Case 2:} Some student gets $\ge 6$ pieces. $$N\le \frac{11}{5}\times\frac{1}{6}=\frac{11}{30}<\frac{13}{30}.$$ \pause \smallskip \isblue{\bf Case 3:} Some student gets $\le 3$ pieces. One of the pieces is $$\ge \frac{11}{5}\times\frac{1}{3}=\frac{11}{15}.$$ \pause Look at the muffin it came from to find a piece that is $$\le 1-\frac{11}{15}=\frac{4}{15}<\frac{13}{30}.$$ \medskip \pause (\isred{Negation of Cases 2 and 3:} Every student gets 4 or 5 pieces.) \end{frame} \begin{frame}\frametitle{\bf \boldmath{$f(11,5) = \frac{13}{30}$}, Fun Cases} \vspace{-30pt} \isblue{\bf Case 4:} Every muffin is cut in 2 pieces, every student gets 4 or 5 pieces. Number of pieces: 22. Note $\le 11$ pieces are $>\frac{1}{2}$. \pause \begin{itemize} \item $s_4$ is number of students who get 4 pieces \item $s_5$ is number of students who get 5 pieces \end{itemize} \pause \[ \begin{array}{rl} 4s_4+ 5s_5 & = 22\cr s_4 + s_5 & = 5 \cr \end{array} \] \pause $s_4=3$: There are 3 students who have 4 shares. $s_5=2$: There are 2 students who have 5 shares. \bigskip \pause We call a share that goes to a person who gets 4 shares a \isred{4-share}. We call a share that goes to a person who gets 5 shares a \isred{5-share}. \end{frame} \begin{frame}\frametitle{\bf \boldmath{$f(11,5) = \frac{13}{30}$}, Fun Cases} %$\diamond$ and $\circ$ are pieces. \isblue{Case 4.1:} Some 4-share is $\le \frac{1}{2}$. Alice gets $w\le x\le y\le z$ and $w\le \frac{1}{2}$. Since $w+x+y+z=\frac{11}{5}$ and $w\le \frac{1}{2}$ $$x+y+z \ge \frac{11}{5} - \frac{1}{2} = \frac{17}{10}$$ \pause $$z \ge \frac{17}{10}\times\frac{1}{3} = \frac{17}{30}$$ \pause Look at \isred{buddy} of $z$. $$B(z) \le 1-z = 1 - \frac{17}{30} = \frac{13}{30}$$ \pause GREAT! This is where $\frac{13}{30}$ comes from! \end{frame} \begin{frame}\frametitle{\bf \boldmath{$f(11,5) = \frac{13}{30}$}, Fun Cases} \isblue{Case 4.2:} All 4-shares are $>\frac{1}{2}$. There are $4s_4=12$ 4-shares. There are $\ge 12$ pieces $>\frac{1}{2}$. Can't occur. \end{frame} \begin{frame}\frametitle{\bf INT Method} Proof that $f(11,5) \le \frac{13}{30}$ was an example of the HALF method. \bigskip \pause FC or HALF worked on everything with $s=3,4,5,\ldots,23$. \bigskip \pause Then we found a case where neither FC nor HALF worked. \bigskip \pause We found a new method: INT. \end{frame} \begin{frame}\frametitle{\bf More Sophisticated INT: \boldmath{$f(24,11)\le \frac{19}{44}$}} Assume $(24,11)$-procedure with smallest piece $>\frac{19}{44}$. Can assume all muffin cut in two and all student gets $\ge 2$ shares. We show that there is a piece $\le \frac{19}{44}$. \pause \bigskip \isblue{Case 1:} A student gets $\ge 6$ shares. Some piece $\le \frac{24}{11\times 6}<\frac{19}{44}$. \pause \bigskip \isblue{Case 2:} A student gets $\le 3$ shares. Some piece $\ge \frac{24}{11\times 3}=\frac{8}{11}$. Buddy of that piece $\le 1-\frac{8}{11} \le \frac{3}{11}<\frac{19}{44}$. \pause \bigskip \isblue{Case 3:} Every muffin is cut in 2 pieces and every student gets either 4 or 5 shares. Total number of shares is 48. \end{frame} \begin{frame}\frametitle{\bf How many students get 4? 5? Where are Shares?} {\it 4-students:} a student who gets 4 shares. $s_4$ is the number of them. {\it 5-students:} a student who gets 5 shares. $s_5$ is the number of them. \bigskip \pause {\it 4-share:} a share that a 4-student who gets. {\it 5-share:} a share that a 5-student who gets. \bigskip \pause \[ \begin{array}{rlc} 4s_4+5s_5 & = 48&\cr s_4+s_5 & = 11 &%\hbox{ Get $s_4=7$ and $s_5=4$}\cr \end{array} \] \bigskip \pause $s_4=7$. Hence there are $4s_4=4\times 7 = 28$ 4-shares. $s_5=4$. Hence there are $5s_5=5\times 4=20$ 5-shares. \end{frame} \begin{frame}\frametitle{\bf Case 3.1 and 3.2: Too Big or Too Small} \pause \isblue{Case 3.1:} There is a share $\ge \frac{25}{44}$. Then its buddy is $$\le 1-\frac{25}{44} = \frac{19}{44}$$ \pause \bigskip \isblue{Case 3.2:} There is a share $\le \frac{19}{44}$. Duh. \pause Henceforth assume that all shares are in $$\biggl (\frac{19}{44},\frac{25}{44}\biggr )$$ \[ \begin{array}{ccccccc} ( & & & & & & ) \cr \frac{19}{44} & & & & & & \frac{25}{44}\cr \end{array} \] \end{frame} \begin{frame}\frametitle{\bf Case 3.3: Some 5-shares \boldmath{$\ge \frac{20}{44}$}} {\it 5-share:} a share that a 5-student who gets. \isblue{Claim:} If some 5-shares is $\ge \frac{20}{44}$ then some share $\le \frac{19}{44}$. \pause \isblue{Proof:} Assume Alice has $v\le w\le x\le y\le z$ and $z\ge \frac{20}{44}$. \pause Since $v+w+x+y+z=\frac{24}{11}$ and $z\ge \frac{20}{44}$ \pause $$v+w+x+y \le \frac{24}{11}-\frac{20}{44}= \frac{76}{44}$$ \pause $$v\le \frac{76}{44}\times\frac{1}{4} = \frac{19}{44}$$ \pause Henceforth we assume all 5-shares are in $\biggl (\frac{19}{44},\frac{20}{44}\biggr ).$ \pause \isblue{Recall:} there are $5s_5= 5\times 4 = 20$ 5-shares. \[ \begin{array}{ccccccc} ( &\hbox{20 5-shs}& )[ & & & & ) \cr \frac{19}{44} & &\frac{20}{44}& & & & \frac{25}{44}\cr \end{array} \] \pause \end{frame} \begin{frame}\frametitle{\bf Case 3.4: Some 4-shares \boldmath{$\le \frac{21}{44}$}} {\it 4-share:} a share that a 4-student who gets. \isblue{Claim:} If some 4-shares is $\le \frac{21}{44}$ then some share $\le \frac{19}{44}$. \pause \isblue{Proof:} Assume Alice has $w\le x\le y\le z\le $ and $w\le \frac{21}{44}$. \pause Since $w+x+y+z=\frac{24}{11}$ and $w\le \frac{21}{44}$ \pause $$x+y+z \ge \frac{24}{11}-\frac{21}{44}= \frac{75}{44}$$ \pause $$z\ge \frac{75}{44}\times\frac{1}{3} = \frac{25}{44}$$ \pause The buddy of $z$ is of size $$\le 1-\frac{25}{44} = \frac{19}{44}$$ \pause Henceforth we assume all 4-shares are in $$\biggl (\frac{21}{44},\frac{25}{44}\biggr ).$$ \end{frame} \begin{frame}\frametitle{\bf Case 3.5: All Shares in Their Proper Intervals} \isblue{Case 3.5:} 4-shares in $(\frac{21}{44},\frac{25}{44})$, 5-shares in $(\frac{19}{44},\frac{20}{44})$. \pause \isblue{Recall:} there are $4s_4 = 4\times 7 = 28$ 4-shares. \isblue{Recall:} there are $5s_5= 5\times 4 = 20$ 5-shares. \pause \[ \begin{array}{ccccccc} ( &\hbox{20 5-shs}& )[ &\hbox{0 shs}& ]( &\hbox{28 4-shs}& ) \cr \frac{19}{44} & &\frac{20}{44}& & \frac{21}{44} & & \frac{25}{44}\cr \end{array} \] \end{frame} \begin{frame}\frametitle{\bf More Refined Picture of What is Going On} \[ \begin{array}{ccccccc} ( &\hbox{20 5-shs}& )[ &\hbox{0 shs}& ]( &\hbox{28 4-shs}& ) \cr \frac{19}{44} & &\frac{20}{44}& & \frac{21}{44}& & \frac{25}{44}\cr \end{array} \] \pause \noindent \isred{Claim 1:} There are no shares $x\in [\frac{23}{44},\frac{24}{44}]$. \pause \bigskip If there was such a share then buddy is in $[\frac{20}{44},\frac{21}{44}].$ QED. \pause The following picture captures what we know so far. \[ \begin{array}{ccccccccccc} (&\hbox{20 5-shs}&)[ &\hbox{0}&]( &\hbox{8 S4-shs}&)[ &\hbox{0}&]( &\hbox{20 L4-shs}&) \cr \frac{19}{44}& &\frac{20}{44}& & \frac{21}{44}& &\frac{23}{44}& &\frac{24}{44} & &\frac{25}{44} \cr \end{array} \] \pause S4= Small 4-shares L4= Large 4-shares. L4 shares, 5-share: \isred{buddies}, so $|$L4$|$=20. \end{frame} \begin{frame}\frametitle{\bf Diagram} \[ \begin{array}{ccccccccccc} (&\hbox{20 5-shs}&)[ &\hbox{0}&]( &\hbox{8 S4-shs}&)[ &\hbox{0}&]( &\hbox{20 L4-shs}&) \cr \frac{19}{44}& &\frac{20}{44}& & \frac{21}{44}& &\frac{23}{44}& &\frac{24}{44} & &\frac{25}{44} \cr \end{array} \] \pause \isred{Claim 2:} Every 4-student has at least 3 L4 shares. \bigskip \pause If a 4-student had $\le 2$ L4 shares then he has $$<2\times \biggl (\frac{23}{44}\biggr ) + 2\times \biggl (\frac{25}{44}\biggr ) =\frac{24}{11}.$$ \pause \isred{Contradiction:} Each 4-student gets $\ge 3$ L4 shares. \pause There are $s_4=7$ 4-students. \pause Hence there are $\ge 21$ L4-shares. \pause But there are only 20. \end{frame} \begin{frame}\frametitle{\bf Other Techniques} Here are the list of the Techniques we came up with: \begin{enumerate} \item Floor-Ceiling \item Half \item INT \item GAP \item Easy buddy-match \item Hard buddy-match \item Train (only worked on 3 $(m,s)$'s). \end{enumerate} \bigskip \pause Time to say we are NOT going to find a finite set of techniques that covers all cases and take what we got and write a book. \end{frame} \begin{frame}\frametitle{\bf Later Results by Other People} \begin{enumerate} \item In Fall 2018 Scott Huddleston emailed me code for an algorithm that, on input $m,s$, found $f(m,s)$ REALLY FAST. \item Jacob and Erik Understand WHAT his algorithm does and Jacob coded it up to make sure he understood it. Jacob's code is also REALLY FAST. \item Neither Scott, Bill, Jacob, or Erik had a proof that Scott's algorithm was fast (poly in $m,s$). \item Richard Chatwin independently came up with the same algorithm; however, he also has a proof that it works. Its on arXiv. \item One corollary of the work: $f(m,s)$ only depends on $m/s$. \end{enumerate} \end{frame} \begin{frame}\frametitle{\bf How Our Book Worked} \pause We all had tasks we were good at and did those: \begin{enumerate} \pause \item Erik: A Math Genius (solves muffin problems) \pause \item Jacob and Daniel: Programmers (codes up techniques) \pause \item Bill: The Mastermind (guides the work and writes it up) \end{enumerate} \pause We also all could do some of the other tasks. \end{frame} \begin{frame}\frametitle{\bf How it worked} We kept increasing $s$. \begin{enumerate} \pause \item Bill tells Erik the least case we can't do. \pause Example: \isred{Erik, our techniques do not work on (35,13).} \pause \item Erik solves and sends Bill a 1-page sketch. \pause \item Bill fills in the details and obtains general technique. \pause \item Jacob \& Daniel code up technique and find least case that can't be done. For example \isred{ We can't do (47,23).} \pause \item Sends to Bill who either does it or \pause Goto Step 1. \end{enumerate} \pause This happened 7 times leading to techniques now called: \pause Floor Ceiling, \pause Half, \pause Int, \pause Midpoint, \pause Gaps, \pause Easy Buddy-Match, \pause Hard buddy-Match, \pause Train \pause \bigskip Also a chapter that sketched out Scott H's method. \end{frame} \begin{frame}\frametitle{\bf I meet Alan Frank!} I emailed Alan Frank, the \isred{creator} of the Muffin Problem and we planned to meet at the MIT combinatorics seminar where I was scheduled to give a talk. \begin{itemize} \pause \item He was delighted that his innocent problem, that he viewed as recreational, has lead to so much math of interest. \pause \item He brought to the seminar 11 muffins: 1 cut $(\frac{15}{30},\frac{15}{30})$, 2 cut $(\frac{14}{30},\frac{16}{30})$, 8 cut $(\frac{13}{30},\frac{17}{30})$. \pause The five us of took pieces so we each got $\frac{11}{5}$ muffins. \pause \item He does a Bike-For-Food Charity. I asked him if I should give \$40.00 a year OR my Royalties. He chose the \$40.00. \pause First Year Royalties: \$50.00 \pause Second Year Royalties: \$40.00 \pause Third Year and beyond Royalties: $\le \$20.00$ \end{itemize} \end{frame} \begin{frame}\frametitle{\bf Final Thoughts and Advice} \begin{enumerate} \pause \item I got this problem \isred{from a pamphlet}. Look around you! Inspiration can come from anywhere! \pause \item When I could not solve a muffin problem I got help. \isred{Do not be shy about asking for help}. \pause \item The co-authors were a diverse collection of strengths as mentioned before. This worked because \pause \centerline{\isred{Team Work Makes the Dream Work!}} \end{enumerate} \end{frame} \end{document}