[math-fun] Remez Principle for lexically optimal muffin solutions
David Moulton described an appealing criterion for a unique optimal solution to muffin problems -- order the pieces of the corefinement in nondecreasing size, and choose the lexicographically largest solution. I'll call this the "lexically optimal" solution. Any solution to the original problem, which only requires maximizing the smallest piece, I call a "weak optimum". In this note I present some weak optimal solutions together with (what I believe are) their lexically optimal solutions. These examples are intended to illustrate a principle I now formulate and conjecture: Muffin Remez Principle: The lexically optimal solution to a muffin problem is found by distributing non-unifomity with maximal evenness at every stage of solution construction. I chose this name by imperfect analogy with the Remez algorithm in numerical analysis. Example 1: Instances 3/2 < r < 2 are usually given with either 3 or 4 pieces per person. But S(15/8) = 3/8 = 1-r/3 = r/5 admits a weak optimum with either 3 or 5 pieces per person: 1/8 * { [3,5]*15; [3*5]*3; [5*3]*5 } The lexical optimum is 1/8 * { [3,5]*6, [4*2]*9; [3,4*3]*6; [5*3]*2 } which exceeds the weak optimum at the 7th piece, 4/8 > 3/8. Example 2: Lexical optima in 3/2 < r < 2 minimize the number of muffins with both halves in 3-parts or 4-parts. S(17/10) = 2/5 = (5-2r)/4 = (2r-1)/6 admits a weak optimum with muffins concentrated in both 3-parts and 4-parts: 1/10 * { [4,6]*12, [5*2]*5; [4*3,5]*4; [6*2,5]*6 } The lexical optimum concentrates all unshared muffins in 3-parts: 1/30 * { [12,18]*4, [13,7]*12, [15*2]; [12,13*3]*4; [18*2,15]*2, [17*3]*4 } and exceeds the weak optimum at the 5th piece, 13/30 > 4/10. Example 3: All 9/5 < r < 2 admit optimal solutions using unsplit muffins, but these are usually weak. Consider S(11/6) = 7/18 = 1-r/3 A weak optimum using unsplit muffins is 1/18 * { [7,11]*6, [8,10]*2, [9*2], [18]*2; [7*2,9,10]*2, [7,8,18]*2; [11*3]*2 } Its lexical optimum is 1/36 * { [14,22]*6, [17,19]*4, [18*2]; [14*2,19*2]*2, [14,17*2,18]*2; [22*3]*2 } which exceeds the weak optimum at the 7th piece, 17/36 > 8/18.
On Mon, 9 Mar 2009, Huddleston, Scott wrote:
David Moulton described an appealing criterion for a unique optimal solution to muffin problems -- order the pieces of the corefinement in nondecreasing size, and choose the lexicographically largest solution. I'll call this the "lexically optimal" solution. Any solution to the original problem, which only requires maximizing the smallest piece, I call a "weak optimum".
In this note I present some weak optimal solutions together with (what I believe are) their lexically optimal solutions. These examples are intended to illustrate a principle I now formulate and conjecture:
Muffin Remez Principle: The lexically optimal solution to a muffin problem is found by distributing non-unifomity with maximal evenness at every stage of solution construction.
Yes, I guess this is what I've been doing when looking for lexically optimal partitions, but can you make this more precise?
Example 1: Instances 3/2 < r < 2 are usually given with either 3 or 4 pieces per person. But
S(15/8) = 3/8 = 1-r/3 = r/5
...
The lexical optimum is
1/8 * { [3,5]*6, [4*2]*9; [3,4*3]*6; [5*3]*2 }
In fact, the lexical optimum, which I gave in a previous note is 3 * 6, 4 * 6, 5 * 6, 8 * 6, or, in your notation, 1/8 * { [3,5]*6, [4*2]*3, [8]*6; [3,4,8]*6, [5*3]*2 }. Another interesting example is (3, 8). The optimal partition is 4/3 * 6, 5/3 * 6, 3 * 2 a.k.a. 1/9 * { [4,5]*6, [9]*2; [4*6]; [5*3,9]*2 }, in which each person gets either 4 or 6 pieces. In general, when you're looking for lexical optima, you can start by assume that every muffin is split into 2 pieces (unless 4m/3 < n < 3m/2) and go from there (unless it doesn't work, in which case you might have to consider cutting a muffin into 3), but at the end, you have to see whether some of your half muffins fuse back into whole muffins.
Example 2: Lexical optima in 3/2 < r < 2 minimize the number of muffins with both halves in 3-parts or 4-parts.
S(17/10) = 2/5 = (5-2r)/4 = (2r-1)/6
admits a weak optimum with muffins concentrated in both 3-parts and 4-parts:
1/10 * { [4,6]*12, [5*2]*5; [4*3,5]*4; [6*2,5]*6 }
The lexical optimum concentrates all unshared muffins in 3-parts:
1/30 * { [12,18]*4, [13,7]*12, [15*2]; [12,13*3]*4; [18*2,15]*2, [17*3]*4 }
The "7" should be "17". Also, can you explain what you mean by "concentrate"?
Example 3: All 9/5 < r < 2 admit optimal solutions using unsplit muffins,
I'm guessing this is a conjecture of yours, not a theorem.
but these are usually weak.
The (8, 15) lexically optimal partition above has unsplit muffins. David P. Moulton
participants (2)
-
David P. Moulton -
Huddleston, Scott