On Saturday 17 January 2009, Dan Asimov wrote:
The muffin problem is fascinatingly both simple to ask and hard to solve.
In spirit it reminds me of the Egyptian Fraction Problem, to not only represent the arbitrary p/q > 0 as a sum of distinct integer reciprocals (i.e., an Egyptian fraction), but to do so such that the largest denominator used is minimum. ... QUESTION: Is there an algorithm for solving this minimization problem?
USELESS ANSWER: Yes. Here is one. 1. Apply the greedy algorithm. (This always converges, because the numerator of the remainder to be expressed as a sum of distinct reciprocals decreases.) 2. Obviously this gives an upper bound on the minimal largest denominator. Call it D. 3. There are only finitely many sums of distinct reciprocals of positive integers <= D. (Specifically, 2^D of them.) Try them all. So the real question is whether there's a non-useless algorithm for solving the problem. I don't think the answer to that is known. -- g