Re: [math-fun] muffin problem
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. ((( It's well known that the greedy algorithm is not the way to solve this. E.g. -- as found in Wikipedia -- greedily: 5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225, but altruistically: 5/121 = 1/33 + 1/121 + 1/363. ))) QUESTION: Is there an algorithm for solving this minimization problem? As with the muffin problem there is also the question here of which decomposition uses the fewest summands. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
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
On Jan 17, 2009, at 3:44 PM, Dan Asimov wrote:
The muffin problem is fascinatingly both simple to ask and hard to solve.
But where exactly are the hard instances? As Mike Reid has shown, keeping m fixed and small, the problem can be solved for arbitrary n. On the other hand, we know U(m, m) = m and also U(3k-1, 3k) = k. The latter saturates the bound I proved earlier and the partitions that realize the bound have a very simple structure. For example, here is the array of x_{ij} values for the case k = 3: 333000000 500400000 050040000 005004000 000400500 000040050 000004005 000000333 For the general case the diagonally running non-zeroes range from k to 2k-1 in blocks of three (one increasing, the other decreasing) and the first and last rows have three k's. It wouldn't surprise me if other cases near the diagonal of the m,n plane also had simple solutions. Veit
participants (3)
-
Dan Asimov -
Gareth McCaughan -
Veit Elser