Alan Frank (a friend of mine and Andy Latto's) asks, what's the best way to divide m identical muffins among n people, so that each person gets the same amount of muffin (receiving either one piece of size m/n or several pieces whose sizes add up to m/n), where "best" means "so as to maximize the size of the smallest piece". For example, if 4 muffins are to be divided among 7 people, and if each piece has size of the form i/7 for some i, then it is easy to show that one of the pieces must have size 1/7 (it isn't possible for everyone to get either 4/7 or 2/7+2/7). But we can improve on this by dividing two of the muffins 5:5:4 and dividing the other two 3:3:8 and then giving everyone either 5/14+3/14, 4/14+4/14, or 8/14 of a muffin; this is better since the smallest piece has size 3/14 > 1/7. Jim Propp
For the 4/7 problem, split two of the muffins into 1/3s, and the other two into 3 * 5/21 + 2/7. Six of the parties get 1/3 + 5/21, and the last gets 2/7 + 2/7. Minimum size is 5/21, > 3/14. Rich ------------ Quoting James Propp <jpropp@cs.uml.edu>:
Alan Frank (a friend of mine and Andy Latto's) asks, what's the best way to divide m identical muffins among n people, so that each person gets the same amount of muffin (receiving either one piece of size m/n or several pieces whose sizes add up to m/n), where "best" means "so as to maximize the size of the smallest piece".
For example, if 4 muffins are to be divided among 7 people, and if each piece has size of the form i/7 for some i, then it is easy to show that one of the pieces must have size 1/7 (it isn't possible for everyone to get either 4/7 or 2/7+2/7). But we can improve on this by dividing two of the muffins 5:5:4 and dividing the other two 3:3:8 and then giving everyone either 5/14+3/14, 4/14+4/14, or 8/14 of a muffin; this is better since the smallest piece has size 3/14 > 1/7.
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hello, The Birthday problem is usually cast in terms of finding the number of people at which the probability that at least two have the same birthday is equal to (or just more than) 1/2. It's fairly straightforward, using Stirling's approximation, to show that this is approx sqrt(2 ln(2) n), where n is the number of possible birthdays. A book that I have says that the expected number of tries, which can be different (substantially, depending on the probability distribution) from the point at which the probability equals 1/2, is approx sqrt( pi n / 2), which, in this case is fairly close to the above expression, but not equal. I can show that the exact value is 2*(1/n) + 3*(2/n)*n!/(n-2)!/n^2 + 4*(3/n)*n!/(n-3)!/n^3 + ... Apparently, this can be shown to equal Sum_{k=0}^n n!/(n-k)!/n^k It can also be shown to be approximately Int_0^n (1 - t/n)^(t-n) e^(-t) t^2 / n dt I'm not great at finding asymptotic expansions--does anyone know how to show that, say, the integral is approx sqrt( pi n / 2), or that the sums are equal and approx the sqrt expression? Thanks, Bill C.
participants (3)
-
Cordwell, William R -
James Propp -
rcs＠xmission.com