Search

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), Comment: Paper is outdated and some parts are wrong. There will be a book on this topic soon which will be THE place to get this information!

Assume you an infinite supply of pennies, nickels, dimes, and quarters (or some other finite set of denominations which are relatively prime). Let CH(n) be the number of ways to make change of n cents. We present a simple unified exposition of three know theorems about CH(n). Let M be the LCM of a1,...,aL. Let M' be the LCM of the GCD of all pairs of ai's. (1) If 0\le r\le M-1 then CH(n) restricted to n \equiv r mod M is a poly, (2) If 0\le r\le M'-1 then CH(n) restricted to n\equiv r mod M' is a poly except for the constant term, (3) CH(n) is n^{L-1}/(L-1)!a1a2...aL + O(n^{L-2}). Part (3) is known as Schur's theorem.