The Muffin Problem

You have \(m\) muffins and \(s\) students. You want to divide the muffins into pieces and give the shares to students such that every student has \(\frac{m}{s}\) muffins. Find a divide-and-distribute protocol that maximizes the minimum piece. Let \(f(m,s)\) be the minimum piece in the optimal protoc...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-07
Main Authors: Cui, Guangiqi, Dickerson, John, Durvasula, Naveen, Gasarch, William, Metz, Erik, Prinz, Jacob, Raman, Naveen, Smolyak, Daniel, Yoo, Sung Hyun
Format: Article
Language:English
Subjects:
Formulas (mathematics)
Students
Theorems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:You have \(m\) muffins and \(s\) students. You want to divide the muffins into pieces and give the shares to students such that every student has \(\frac{m}{s}\) muffins. Find a divide-and-distribute protocol that maximizes the minimum piece. Let \(f(m,s)\) be the minimum piece in the optimal protocol. We prove that \(f(m,s)\) exists, is rational, and finding it is computable (though possibly difficult). We show that \(f(m,s)\) can be derived from \(f(s,m)\); hence we need only consider \(m\ge s\). We give a function \(FC(m,s)\) such that, for \(m\ge s+1\), \(f(m,s)\le FC(m,s)\). It is often the case that \(f(m,s)=FC(m,s)\). More formally, for all \(s\), for all but a finite number of \(m\), \(f(m,s)=FC(m,s)\). This leads to a nice formula for \(f(m,s)\), though there are exceptions to it. We give a formula \(INT(m,s)\), which has 6 parts, such that for many of the exceptional \(m\), \(f(m,s)=INT(m,s)
ISSN:2331-8422