Hi muffin-folk, Now I'll give the table of all the optimal partitions I've computed for the muffin problem, namely those with m and n relatively prime with mn < 128, followed by some comments. Recall that I normalize to find common partitions of m * n and n * m and that I write multiplicities after parts. Recall also that I'm lexically maximizing the list of piece sizes sorted in nondecreasing order. That is, I maximize the smallest piece, then the next smallest, etc. I give (m, n) and then the (unique) optimal partition, in increasing order. Thus the value of U(m, n) is just the first number after the colon. I repeat (m, m+1) pairs in the explicit list after the general formulas. (1, k): 1 * k (for k>=1) (2, 2k+1): 1 * 2, 2 * 2k (for k>=0) (3, 3k+-1): (3k-1)/2k * 2k, (3k+1)/2k * 2k, 3 * (k+-1) (for k>=1 odd) (3, 3k+-1): (3k-1)/2k * 2k, 3/2 * 2, (3k+1)/2k * 2k, 3 * (k-1+-1) (for k>=2 even) (4, 2k+1): (2k-1)/k * 2k, 2 * 2, (2k+1)/k * 2k (for k>=1) (3k-1, 3k): k * 6, (k+1) * 6, ..., (2k-1) * 6 (for k>=2) (3k, 3k+1): k * 2, (2k+1)/2 * 4, (k+1) * 2, ..., 2k * 2 (for k>=2) (3k+1, 3k+2): (2k+1)/2 * 4, (k+1) * 2, (2k+3)/2 * 4, ..., (4k+1)/2 * 4 (for k>=1) (5, 6): 2 * 6, 3 * 6 (5, 7): 5/3 * 3, 7/3 * 6, 8/3 * 6 (5, 8): 2 * 4, 3 * 4, 5 * 4 (5, 9): 2 * 6, 3 * 6, 5 * 3 (5, 11): 13/6 * 6, 9/4 * 4, 5/2 * 2, 11/4 * 4, 17/6 * 6 (5, 12): 2 * 4, 3 * 4, 5 * 8 (5, 13): 13/6 * 6, 22/9 * 6, 5/2 * 2, 23/9 * 6, 17/6 * 6 (5, 14): 11/5 * 10, 12/5 * 2, 13/5 * 2, 14/5 * 10, 5 * 2 (5, 16): 16/7 * 14, 17/7 * 2, 18/7 * 2, 19/7 * 14 (5, 17): 13/6 * 6, 37/15 * 10, 5/2 * 2, 38/15 * 10, 17/6 * 6 (5, 18): 9/4 * 8, 5/2 * 4, 11/4 * 8, 5 * 8 (5, 19): 16/7 * 14, 69/28 * 4, 5/2 * 2, 71/28 * 4, 19/7 * 14 (5, 21): 7/3 * 18, 8/3 * 18, 5 * 3 (5, 22): 9/4 * 8, 5/2 * 4, 11/4 * 8, 5 * 12 (5, 23): 23/10 * 10, 149/60 * 12, 5/2 * 2, 151/60 * 12, 27/10 * 10 (5, 24): 7/3 * 18, 8/3 * 18, 5 * 6 (6, 7): 2 * 2, 5/2 * 4, 3 * 2, 7/2 * 4, 4 * 2 (6, 11): 7/3 * 6, 17/6 * 4, 3 * 2, 19/6 * 4, 11/3 * 6 (6, 13): 13/5 * 10, 14/5 * 2, 3 * 2, 16/5 * 2, 17/5 * 10 (6, 17): 13/5 * 10, 44/15 * 6, 3 * 2, 46/15 * 6, 17/5 * 10 (6, 19): 19/7 * 14, 41/14 * 4, 3 * 2, 43/14 * 4, 23/7 * 14 (7, 8): 5/2 * 4, 3 * 2, 7/2 * 4, 4 * 2, 9/2 * 4 (7, 9): 5/2 * 6, 3 * 2, 7/2 * 2, 4 * 2, 9/2 * 6 (7, 10): 7/3 * 3, 19/6 * 6, 10/3 * 2, 7/2 * 2, 11/3 * 2, 23/6 * 6 (7, 11): 11/4 * 4, 13/4 * 2, 27/8 * 4, 7/2 * 2, 29/8 * 4, 15/4 * 2, 17/4 * 4 (7, 12): 3 * 12, 4 * 12 (7, 13): 8/3 * 6, 19/6 * 2, 41/12 * 4, 7/2 * 2, 43/12 * 4, 23/6 * 2, 13/3 * 6 (7, 15): 3 * 10, 4 * 10, 7 * 5 (7, 16): 3 * 12, 4 * 12, 7 * 4 (7, 17): 11/4 * 4, 17/5 * 10, 69/20 * 2, 7/2 * 2, 71/20 * 2, 18/5 * 10, 17/4 * 4 (7, 18): 3 * 6, 4 * 6, 7 * 12 (8, 9): 3 * 6, 4 * 6, 5 * 6 (8, 11): 8/3 * 6, 11/3 * 6, 4 * 6, 13/3 * 6 (8, 13): 13/4 * 8, 7/2 * 2, 15/4 * 2, 4 * 2, 17/4 * 2, 9/2 * 2, 19/4 * 8 (8, 15): 3 * 6, 4 * 6, 5 * 6, 8 * 6 (9, 10): 3 * 2, 7/2 * 4, 4 * 2, 9/2 * 4, 5 * 2, 11/2 * 4, 6 * 2 (9, 11): 13/4 * 4, 7/2 * 2, 15/4 * 4, 9/2 * 2, 21/4 * 4, 11/2 * 2, 23/4 * 4 (9, 13): 3 * 3, 4 * 6, 5 * 6, 9 * 6 (9, 14): 7/2 * 4, 17/4 * 8, 9/2 * 4, 19/4 * 8, 11/2 * 4 Recall the upper bound I mentioned previously: Corollary. For m < n with m not dividing 2n we have U(m, n) <= m/3 for 4m/3 <= n < 3m/2 U(m, n) <= min( n/([2n/m]+1), m - n/[2n/m] ) otherwise. This upper bound seems to be sharp in many cases. In particular, among all the values in the table above, the only cases when it isn't sharp are (m, m+1) (with m mod 3 not 2), (5, 11), and (9, 11). I imagine the counterexamples will be more common for larger values, and yes, I do think it's a coincidence that the two sporadic counterexamples so far have n=11. Anyway, I thought I would give proofs for those two pairs. For (5, 11), we may, as usual, assume that each 5 splits into exactly 2 pieces, so that there are 22 pieces in all. Splitting an 11 into at least 6 pieces gives parts that are too small, and splitting an 11 into only 3 pieces gives parts whose complements in 5 are too small. So each 11 splits into 4 or 5 pieces, and of the five 11s, there are 3 that split into 4 pieces and 2 that split into 5 pieces. Now all 22 pieces pair up to make the 5s, and since there are 12 pieces coming from 11s split into 4 parts, but only 10 pieces from 11s split into 5 parts, there must be two of the former that pair up. But now consider the 8 pieces making up the two corresponding 11s split into 4 parts. These 8 pieces sum to 11 * 2 = 22, but 2 of them sum to 5, so the remaining 6 sum to 17, and one of them must be at least 17/6. Finally, the complement of this piece in its 5 is at most 13/6. Now consider (9, 11). Again, we may assume that each 9 splits into exactly 2 parts, so there are 22 pieces in all. Each 11 splits into 2 or 3 parts, so 5 of them split into 2 parts, and the other 4 split into 3 parts. Again, two pieces from two of the 11s that split into 3 must be paired to give a 9. Then the other 4 pieces of those 11s sum to 11 * 2 - 9 = 13, and the smallest of them is at most 13/4. Okay, now that I look at the proofs, I think it's not so much coincidence, since it's almost the same argument with the same numbers. David P. Moulton