editor
178
edits
Changes
From Theory
Created page with "== Title == The Muffin Problem == Speaker == William Gasarch == Abstract == By Guangqi Cui, Naveen Durvasula, William Gasarch, Naveen Raman, Sung Hyun Yoo Consider the foll..."
== Title ==
The Muffin Problem
== Speaker ==
William Gasarch
== Abstract ==
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.
The Muffin Problem
== Speaker ==
William Gasarch
== Abstract ==
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.
