\makeatletter\let\ifGm@compatii\relax\makeatother \documentclass[red]{beamer} %\usepackage{beamerthemesplit} \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{ {Guangi Cui - Montgomery Blair HS}\\ {John Dickerson- University of MD}\\ {Naveen Durvasula - Montgomery Blair HS}\\ {William Gasarch - University of MD}\\ {Erik Metz - University of MD}\\ {Jacob Prinz-University of MD}\\ {Naveen Raman - Richard Montgomery HS }\\ {Daniel Smolyak- University of MD}\\ {Sung Hyun Yoo - Bergen County Academies (in NJ) }\\ } \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 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 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 Mixed Int Program (in paper). \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 \isred{All done by hand, no use of a computer} \isred{by Co-author Erik Metz is a} \isblue{muffin savant} ! \bigskip 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 \boldmath{$f(3,5) \ge $?}} Clearly $f(3,5) \ge \frac{1}{5}$. \isblue{Can we get $\bm{f(3,5)>\frac{1}{5}}$?} \isred{Work on it with your neighbor} \end{frame} \begin{frame}\frametitle{\bf \boldmath{$f(3,5)\ge \frac{1}{4}$}} $f(3,5)\ge \frac{1}{4}$ \begin{enumerate} \item Divide 2 muffin $[\frac{6}{20},\frac{7}{20},\frac{7}{20}]$ \item Divide 1 muffin $[\frac{5}{20},\frac{5}{20},\frac{5}{20},\frac{5}{20}]$ \item Give 4 students $(\frac{5}{20},\frac{7}{20})$ \item Give 1 students $(\frac{6}{20},\frac{6}{20})$ \end{enumerate} \pause \isblue{Can we do better? } \isred{Work on it with your neighbor} \end{frame} \begin{frame}\frametitle{\bf 3 Muffins, 5 People--Can't Do Better Than \boldmath{$\frac{1}{4}$}} %\vspace{-50pt} \isred{NO WE CAN'T!} There is a procedure for 3 muffins,5 students where each student gets $\frac{3}{5}$ muffins, smallest piece $N$. We want $N\le \frac{1}{4}$. \pause \bigskip \isblue{\bf Case 0:} Alice gets 1 piece of size $\frac{3}{5}$. Look at the rest of that muffin which totals to $\frac{2}{5}$. (1) That piece is cut. Have piece $\le \frac{2}{5}\times\frac{1}{2} = \frac{1}{5}$, OR (2) That piece uncut. So someone gets a $\frac{2}{5}$-piece. Must also get a $\frac{1}{5}$ piece. (\isred{Henceforth:} All people get $\ge 2$ pieces.) \pause \bigskip \isblue{\bf Case 1:} Alice gets $\ge 3$ pieces. Then $N\le\frac{3}{5}\times\frac{1}{3}=\frac{1}{5}$. (\isred{Henceforth:} Everyone gets 2 pieces.) \pause \bigskip \isblue{\bf Case 2:} Everyone gets 2 pieces. 10 pieces, 3 muffins: \isred{Some muffin} gets $\ge 4$ pieces. So some piece is $\le \frac{1}{4}$. \end{frame} \begin{frame}\frametitle{\bf \boldmath{$f(3,5)$} and \boldmath{$f(5,3)$}} $f(5,3)\ge\frac{5}{12}$ \begin{enumerate} \item Divide 4 muffins \isred{$\bm{[\frac{5}{12},\frac{7}{12}]}$} \item Divide 1 muffin \isblue{$\bm{[\frac{6}{12},\frac{6}{12}]}$} \item Give 2 students \isdarkgreen{\bm{$(\frac{6}{12},\frac{7}{12},\frac{7}{12})}$} \item Give 1 students \isorange{$\bm{(\frac{5}{12},\frac{5}{12},\frac{5}{12},\frac{5}{12})}$} \end{enumerate} \pause $f(3,5)\ge \frac{1}{4}$ \begin{enumerate} \item Divide 2 muffin \isdarkgreen{$\bm{[\frac{6}{20},\frac{7}{20},\frac{7}{20}]}$} \pause \item Divide 1 muffin \isorange{$\bm{[\frac{5}{20},\frac{5}{20},\frac{5}{20},\frac{5}{20}]}$} \item Give 4 students \isred{$\bm{(\frac{5}{20},\frac{7}{20})}$} \item Give 1 students \isblue{\isblue{$\bm{(\frac{6}{20},\frac{6}{20})}$}} \end{enumerate} \pause $f(3,5)$ proc is $f(5,3)$ proc but swap Divide/Give and mult by $3/5$. \pause \isred{Duality Theorem:} $f(m,s) = \frac{m}{s} f(s,m)$. \end{frame} \begin{frame}\frametitle{\bf Conventions} \isblue{We know and use the following:} \begin{enumerate} \item By duality can assume $m>s$ \item If $s$ divides $m$ then $f(m,s)=1$ so assume $s$ does not divide $m$. \item All muffins are cut in $\ge 2$ pcs. Replace uncut muff with 2 $\frac{1}{2}$'s \item If assuming $f(m,s)>\alpha >\frac{1}{3}$, assume all muffin in $\le 2$ pcs. \item $f(m,s)>\alpha >\frac{1}{3}$, so exactly 2 pcs, is common case. \end{enumerate} \isred{We do not know this but still use:} $f(m,s)$ only depends on $\frac{m}{s}$. All of our techniques that hold for $(m,s)$ hold for $(Am,As)$. For particular numbers, we only look at $m,s$ rel prime. \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 \}.$$ \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. \bigskip \isblue{\bf Case 1:} Some muffin is cut into $\ge 3$ pieces. Some piece \isred{$\bm{\le \frac{1}{3}}$.} \bigskip \isblue {\bf Case 2:} Every muffin is cut into 2 pieces, so $2m$ pieces. \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}}}}$. \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}}.$ \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 $f(1,3)=\frac{1}{3}$ \bigskip $f(3k,3)=1$. \bigskip $f(3k+1,3)=\frac{3k-1}{6k}$, $k\ge 1$. \bigskip $f(3k+2,3)=\frac{3k+2}{6k+6}$. \bigskip \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 $f(4k,4)=1$ (easy) \bigskip $f(1,4)=\frac{1}{4}$ (easy) \bigskip $f(4k+1,4)=\frac{4k-1}{8k}$, $k\ge 1$. \bigskip $f(4k+2,4)=\frac{1}{2}$. \bigskip $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)$. \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 For $k\ge 1$, $f(5k,5)=1$. \bigskip For $k=1$ and $k\ge 3$, $f(5k+1,5) = \frac{5k+1}{10k+5}$. $f(11,5)$? \bigskip For $k\ge 2$, $f(5k+2,5) = \frac{5k-2}{10k}$. $f(7,5)=\FC(7,5)=\frac{1}{3}$ \bigskip For $k\ge 1$, $f(5k+3,5) = \frac{5k+3}{10k+10}$ \bigskip For $k\ge 1$, $f(5k+4,5)= \frac{5k+1}{10k+5}$ \isred{Note:} A Mod 5 Pattern. \isred{Theorem:} For all $m\ge 5$ \isblue{except m=11}, $f(m,5)=\FC(m,5)$. \end{frame} %\end{document} \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}.$$ 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 (\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}$. \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} \[ \begin{array}{rl} 4s_4+ 5s_5 & = 22\cr s_4 + s_5 & = 5 \cr \end{array} \] $s_4=3$: There are 3 students who have 4 shares. $s_5=2$: There are 2 students who have 5 shares. \bigskip 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,x,y,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}$$ Let $x$ be the largest of $x,y,z$ $$x \ge \frac{17}{10}\times\frac{1}{3} = \frac{17}{30}$$ Look at \isred{buddy} of $x$. $$B(x) \le 1-x = 1 - \frac{17}{30} = \frac{13}{30}$$ 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 INT method. We give a more sophisticated example \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 {\it 4-share:} a share that a 4-student who gets. {\it 5-share:} a share that a 5-student who gets. \bigskip \[ \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 $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. Henceforth assume that all shares are in $$\biggl (\frac{19}{44},\frac{25}{44}\biggr )$$ %XXX \[ \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}$. \isblue{Proof:} Assume that Alice 5 pieces $A,B,C,D,E$ and $E\ge \frac{20}{44}$. Since $A+B+C+D+E=\frac{24}{11}$ and $E\ge \frac{20}{44}$ $$A+B+C+D \le \frac{24}{11}-\frac{20}{44}= \frac{76}{44}$$ Assume $A$ is the smallest of $A,B,C,D$. $$A\le \frac{76}{44}\times\frac{1}{4} = \frac{19}{44}$$ Henceforth we assume all 5-shares are in $\biggl (\frac{19}{44},\frac{20}{44}\biggr ).$ \[ \begin{array}{ccccccc} ( &\hbox{?? 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}$. \isblue{Proof:} Assume that Alice 4 pieces $A,B,C,D$ and $D\le \frac{21}{44}$. Since $A+B+C+D=\frac{24}{11}$ and $D\le \frac{21}{44}$ $$A+B+C \ge \frac{24}{11}-\frac{21}{44}= \frac{75}{44}$$ Assume $A$ is the largest of $A,B,C$. $$A\ge \frac{75}{44}\times\frac{1}{3} = \frac{25}{44}$$ The buddy of $A$ is of size $$\le 1-\frac{25}{44} = \frac{19}{44}$$ 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})$. \[ \begin{array}{ccccccc} ( &\hbox{?? 5-shs}& )[ &\hbox{0 shs}& ]( &\hbox{?? 4-shs}& ) \cr \frac{19}{44} & &\frac{20}{44}& & \frac{21}{44} & & \frac{25}{44}\cr \end{array} \] \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} \] \noindent \isred{Claim 1:} There are no shares $x\in [\frac{23}{44},\frac{24}{44}]$. \bigskip If there was such a share then buddy is in $[\frac{20}{44},\frac{21}{44}].$ \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} \] 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} \] \isred{Claim 2:} Every 4-student has at least 3 L4 shares. \bigskip 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. There are $s_4=7$ 4-students. Hence there are $\ge 21$ L4-shares. But there are only 20. \end{frame} \begin{frame}\frametitle{\bf $\INT$ Technique} $\INT$ is generalization of $f(24,11)\le\frac{19}{44}$ proof. \isred{Definition:} Let $\INT(m,s)$ be the bound obtained. \begin{enumerate} \item $\INT$ proofs can get more complicated than this one. \item $\INT(m,s)$ can be computed in $O(\frac{2m\log m}{s})$. Note: do not need to know the answer ahead of time. \item For $1\le s\le 60$, $s\ob{54}$. By $\INT$-technique methods obtain: $s_3=14$, $s_4=5$. \[ \begin{array}{ccccccccccc} (&\hbox{20 4-shs}&)[ &\hbox{0}&]( &\hbox{22 S3 shs}&)[ &\hbox{0}&]( &\hbox{20 L3-shs}&) \cr \ob{54}& &\ob{55}& & \ob{59}& &\ob{74}& &\ob{78} & &\ob{79} \cr \end{array} \] We just look at the 3-shares: \[ \begin{array}{ccccccccccc} & ( & &\hbox{22 S3 shs}&)[ & &\hbox{0}&]( & &\hbox{20 L3-shs}&) \cr & \ob{59}& & &\ob{74}& & &\ob{78}& & &\ob{79} \cr \end{array} \] \end{frame} \newcommand{\EE}[3]{e({#1},{#2},{#3})} \begin{frame}\frametitle{\bf \boldmath{$\GAPS$} Technique: \boldmath{$f(31,19)\le \ob{54}$}} \[ \begin{array}{ccccccccccc} & ( & &\hbox{22 S3 shs}&)[ & &\hbox{0}&]( & &\hbox{20 L3-shs}&) \cr & \ob{59}& & &\ob{74}& & &\ob{78}& & &\ob{79} \cr \end{array} \] \begin{enumerate} \item $J_1=(\ob{59},\ob{66.5})$ \item $J_2=(\ob{66.5},\ob{74})$ ($|J_1|=|J_2|$) \item $J_3=(\ob{78},\ob{79})$ ($|J_3|=20$) \end{enumerate} \isblue{Note:} Split the shares of size 66.5 between $J_1$ and $J_2$. \isblue{Notation:} An $\EE 1 1 3$ students is a student who has \centerline{a $J_1$-share, a $J_1$-share, and a $J_3$-share.} Generalize to $\EE i j k$ easily. \end{frame} \begin{frame}\frametitle{\bf \boldmath{$\GAPS$} Technique: \boldmath{$f(31,19)\le \ob{54}$}} \begin{enumerate} \item $J_1=(\ob{59},\ob{66.5})$ \item $J_2=(\ob{66.5},\ob{74})$ ($|J_1|=|J_2|$) \item $J_3=(\ob{78},\ob{79})$ ($|J_3|=20$) \end{enumerate} \medskip 1) Only students allowed: $\EE 1 2 3$, $\EE 1 3 3$, $\EE 2 2 2$, $\EE 2 2 3$. All others have either $<\frac{31}{19}$ or $>\frac{31}{19}$. \medskip 2) No shares in $[\ob{61},\ob{64}]$. Look at $J_1$-shares: An $\EE 1 2 3$-student has $J_1$-share $> \frac{31}{19} - \ob{74}-\ob{79}=\ob{64}$. An $\EE 1 3 3$-student has $J_1$-share $< \frac{31}{19} - 2\times\ob{78}=\ob{61}$. \medskip 3) No shares in $[\ob{69},\ob{72}]$: $x\in [\ob{69},\ob{72}]\implies 1-x\in [\ob{61},\ob{64}]$. \end{frame} \begin{frame}\frametitle{\bf \boldmath{$\GAPS$} Technique: \boldmath{$f(31,19)\le \ob{54}$}} \begin{enumerate} \item $J_1=(\ob{59},\ob{61})$ \item $J_2=(\ob{64},\ob{66.5})$ \item $J_3=(\ob{66.5},\ob{69})$ ($|J_2|=|J_3|$) \item $J_4=(\ob{72},\ob{74})$ ($|J_1|=|J_4|$) \item $J_5=(\ob{78},\ob{79})$ ($|J_5|=20$) \end{enumerate} The following are the only students who are allowed. $\EE 1 5 5$. $\EE 2 4 5$, $\EE 3 4 5$. $\EE 4 4 4$. \end{frame} \begin{frame}\frametitle{\bf \boldmath{$\GAPS$} Technique: \boldmath{$f(31,19)\le \ob{54}$}} $\EE 1 5 5$. Let the number of such students be $x$ $\EE 2 4 5$. Let the number of such students be $y_1$ $\EE 3 4 5$. Let the number of such students be $y_2$. $\EE 4 4 4$. Let the number of such students be $z$. 1) $|J_2|=|J_3|$, only students using $J_2$ are $\EE 2 4 5$ -- they use one share each, only students using $J_3$ are $\EE 3 4 5$ -- they use one share each. Hence $y_1=y_2$. We call them both $y$. \medskip 2) Since $|J_1|=|J_4|$, $x=2y+3z$. \medskip 3) Since $s_3=14$, $x+2y+z=14$. \medskip $(2y+3z)+2y+z=14\implies 4(y+z)=14 \implies y+z=\frac{7}{2}$. Contradiction. \end{frame} \begin{frame}\frametitle{\bf \boldmath{$\MATRIX$} Technique: \boldmath{$f(5,3)\ge\frac{5}{12}$}} Want proc for $f(5,3)\ge \frac{5}{12}$. \medskip 1) \isred{Guess} that the only piece sizes are $\frac{5}{12},\frac{6}{12},\frac{7}{12}$ \medskip 2) \isred{Muffin}=pieces add to 1: $\{\frac{6}{12},\frac{6}{12}\}$, $\{\frac{5}{12},\frac{7}{12}\}$. Vectors $\{\frac{6}{12},\frac{6}{12}\}$ is $(0,2,0)$, $m_1$ muffins of this type. $\{\frac{5}{12},\frac{7}{12}\}$ is $(1,0,1)$, $m_2$ muffins of this type. \medskip 3) \isred{Student}=pieces add to $\frac{5}{3}$ $\{\frac{6}{12},\frac{7}{12},\frac{7}{12}\}$ is $(0,1,2)$, $s_1$ students of this type. $\{\frac{5}{12},\frac{5}{12},\frac{5}{12},\frac{5}{12}\}$ is $(4,0,0)$, $s_2$ students of this type. \medskip 4) \isred{Set up equations:} $m_1(0,2,0) + m_2(1,0,1) = s_1(0,1,2)+s_2(4,0,0)$ $m_1+m_2=5$ $s_1+s_2=3$ \medskip \isred{Natural Number Solution}: $m_1=1$, $m_2=4$, $s_1=2$, $s_2=1$ \end{frame} \begin{frame}\frametitle{\bf \boldmath{$\MATRIX$} Technique} Want proc for $f(m,s)\ge \frac{a}{b}$. \medskip 1) \isred{Guess} that the only piece sizes are $\frac{a}{b},\ldots,\frac{b-a}{b}$ \medskip 2) \isred{Muffin}=pieces add to 1: Vectors $\vec v_i$. $x$ types. $m_i$ muffins of type $\vec v_i$ \medskip 3) \isred{Student}=pieces add to $\frac{m}{s}$: Vectors $\vec u_j$. $y$ types. $s_j$ students of type $\vec u_j$ \medskip 4) \isred{Set up equations:} $m_1\vec v_1 + \cdots + m_x\vec v_x = s_1\vec u_1 + \cdots + s_y\vec u_y$ $m_1+\cdots + m_x=m$ $s_1+\cdots + s_y=s$ \medskip 5) \isred{Look for Nat Numb sol.} If find can translate into procedure. \end{frame} \begin{frame}\frametitle{\bf Later Results by Other People} \begin{enumerate} \item In Fall 2018 Scott Huddleston had code for an algorithm that, on input $m,s$, found $f(m,s)$ and the procedure 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 Accomplishment I Am Most Proud of} Accomplishment I Am Most Proud of: \pause \bigskip \isblue{Convinced} \begin{itemize} \item 4 High School students (Guang, Naveen, Naveen, Sunny) \item 3 college student (Erik, Jacob, Daniel) \item 1 professor (John D) \end{itemize} that the most important field of Mathematics is \isred{Muffinry.} \end{frame} \end{document}