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