CATS-Nov-4-2016
Title[edit]
The Muffin Problem
Speaker[edit]
William Gasarch
Abstract[edit]
By Guangqi Cui, Naveen Durvasula, William Gasarch, Naveen Raman, Sung Hyun Yoo
Consider the following problem:
You have 5 muffins and 3 students. You want to divide the muffins evenly so that everyone gets 5/3 of a muffin. You can clearly divide each muffin in 3 pieces and give each person 5/3. NOTE- the smallest piece is of size 1/3.
Is there a procedure where the smallest piece is BIGGER than 1/3?
More genearlly what is the best you can do with m muffins and s students. We have proven many results about this that involve rather complex arguments. We state some of them:
1) For s+1 muffins and s students, if s==0 mod 3 then (a) there is a procedure where the smallest piece is 1/3, and (b) no procedure can do better. (We have results for s==1 and s==2 mod 3 but they are harder to state.)
2) For s=3,4,5,6 and any m we know the answer.
3) For s=7,...,15 and all but a finite number of m we know the answer.
4) Concrete examples: 11 muffins, 5 people then There is a procedure with smallest piece 13/30. There is no better procedure.
5) Concrete example: 16 muffins, 13 people There is a procedure with smallest piece 14/39 There is no better procedure.
