On Wed, 4 Feb 2009, I wrote
Hi muffin choppers,
... I think I have the optimal partition for all cases of (m, m+1),
Okay, now I'll give the general result and proof. Remember that I'm using Veit's U(m, n) notation, looking at a partition of mn that refines both mn = m + m + ... + m and mn = n + n + ... + n). Recall also that I'm trying to find the (unique) maximal partition when the pieces are written in increasing order and partitions are compared lexically. So I want to maximize the smallest piece, given that, maximize the second smallest piece, etc. Finally, recall that I prefer to write multiplicities after parts, so I write "(1/2) * 2" to mean two parts of size 1/2. Theorem: For m >= 4, the optimal corefinement of the partitions m * (m+1) and (m+1) * m of m^2 + m is k * 6, (k+1) * 6, ..., (2k-1) * 6 for m = 3k-1 k * 2, (2k+1)/2 * 4, (k+1) * 2, (2k+3)/2 * 4, ..., 2k * 2 for m = 3k (2k+1)/2 * 4, (k+1) * 2, (2k+3)/2 * 4, ..., (4k+1)/2 * 4 for m = 3k+1. This gives U(3k-1, 3k) = k U(3k, 3k+1) = k U(3k+1, 3k+2) = (2k+1)/2. Alternately, we can write the second part as U(n-1, n) = floor(2n/3)/2, which actually holds for all n >= 3. Proof: First of all, it is straightforward to verify that, in each case, we have a valid refinement of both partitions, so it is enough to assume that we have the optimal refinement and show that it is the one given above. Now we have U(m, m+1) > 1, so every m must be divided into at least 2 pieces, lest the m+1 containing it have a piece of size at most 1. Also, we have U(m, m+1) >= m/3, with only 2 pieces of size m/3 if we have equality, so no m can be divided into 3 or more pieces. Thus every m is divided into exactly 2 pieces, and there are 2m+2 pieces in total. Similarly, every m+1 is divided into 2 or 3 pieces, so it must be the case that two m+1's are divided into 3 pieces, and the rest are divided into 2 pieces. Now we create a graph, whose vertices are the pieces of the refining partition and with two vertices adjacent if they combine to give m or m+1 in one of the original two partitions. (In the original parlance, this means that the corresponding pieces either come from the same muffin or go to the same person.) Then each vertex has exactly one edge of "type m" (meaning its two endpoints combine to give m, or that the corresponding pieces go to the same person), and every vertex, except for the 6 corresponding to the two 3-piece m+1's, has exactly one edge of "type m+1". Note that we have no cycles in this (bipartite) graph, since the sum of the vertices of a 2p-cycle would be both mp (summing over type-m edges) and (m+1)p (summing over type-(m+1) edges). Thus the 2m+2 pieces form exactly three paths with odd length (even number of vertices). If one of these paths has 2p vertices, then the sum of all its vertices is mp, while the sum of its interior vertices is (m+1)(p-1), so the sum of its endpoints is m-p+1. Then one of the endpoints is at most (m-p+1)/2, and if we have equality, then it is straightforward to see that the vertices of the path will have values (m-p+1)/2 * 2, (m-p+3)/2 * 2, ..., (m+p-1)/2 * 2. Given the lengths of the three paths, we lexically maximize the refining partition by choosing equality as above for each path. (Note that the sum of the 6 endpoints is 2m+2 (since the three values of p add up to m+1), so when we make them equal in pairs, we will be able to split them up into two triads, each summing to m+1.) And once we decide to enforce equality, we lexically maximize the refinement by taking the three values of p to be as close to each other as possible, in order to minimize the largest value (and, given this, minimize the second largest value). For the three cases we have p = k, k, k-1 if m = 3k-1 p = k, k, k if m = 3k p = k+1, k, k if m = 3k+1, which give the refinements described above. This verifies optimality and completes the proof. David P. Moulton