[math-fun] Another variant of the muffin problem
Define N(m,s) as *the minimum number of pieces* necessary to distribute m/s muffins to each of s students, starting from m whole muffins. Is N(m,s) easy to determine? —Dan Jim Propp wrote: ----- ... the original muffin problem, f(m,s) (defined as the maximum possible size of the smallest piece among all ways of distributing m muffins among s students) ... -----
I believe N(m,s) = m + s - gcd(m,s) pieces is your answer. This problem is more interesting for multi-way generalizations of the muffin problem. I suspect it is tractable. - Scott On Mon, Aug 24, 2020 at 4:47 PM Dan Asimov <dasimov@earthlink.net> wrote:
Define N(m,s) as *the minimum number of pieces* necessary to distribute m/s muffins to each of s students, starting from m whole muffins.
Is N(m,s) easy to determine?
—Dan
Jim Propp wrote: ----- ... the original muffin problem, f(m,s) (defined as the maximum possible size of the smallest piece among all ways of distributing m muffins among s students) ... -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Scott’s proposed answer corresponds to a greedy construction. Since the RHS is homogeneous under integer scaling, it suffices to consider the case where m and s are relatively prime. If we divide an interval of length ms into m intervals of length s and s intervals of length m, we have (m-1)+(s-1) division-points and hence m+s-1 = m+s-gcd(m,s) pieces. I don’t see how to prove that this is optimal, but maybe my morning coffee will help me see it. Jim On Tue, Aug 25, 2020 at 5:46 AM Scott Huddleston < c.scott.huddleston@gmail.com> wrote:
I believe N(m,s) = m + s - gcd(m,s) pieces is your answer.
This problem is more interesting for multi-way generalizations of the
muffin problem. I suspect it is tractable.
- Scott
On Mon, Aug 24, 2020 at 4:47 PM Dan Asimov <dasimov@earthlink.net> wrote:
Define N(m,s) as *the minimum number of pieces* necessary to distribute
m/s muffins to each of s students, starting from m whole muffins.
Is N(m,s) easy to determine?
—Dan
Jim Propp wrote:
-----
... the original muffin problem, f(m,s) (defined as the maximum possible
size of the smallest piece among all ways of distributing m muffins among s
students) ...
-----
_______________________________________________
math-fun mailing list
math-fun@mailman.xmission.com
https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________
math-fun mailing list
math-fun@mailman.xmission.com
https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Dan Asimov -
James Propp -
Scott Huddleston