Re: [math-fun] muffin problem
i'll do it in the framework of partitions of 1 . define the mesh of a partition to be its smallest part. rich's partition is 5/84 + 5/84 + 5/84 + 5/84 + 5/84 + 5/84 + 1/14 + 1/14 + 1/12 + 1/12 + 1/12 + 1/12 + 1/12 + 1/12 , which has mesh 5/84 , and is simultaneously a refinement of 1/4 + 1/4 + 1/4 + 1/4 and of 1/7 + 1/7 + 1/7 + 1/7 + 1/7 + 1/7 + 1/7 . if some 1/4 is split into 5 or more parts, then the mesh is <= 1/20 < 5/84 . since 1/4 cannot be a part of 1/7 , each 1/4 must be split into at least 2 parts. suppose some 1/4 is split into exactly 2 parts, say 1/4 = a + b , where a <= b . we have 1/8 <= b <= 1/7 , so 3/28 <= a <= 1/8 . now a occurs as a part of 1/7 , so it has another part at most 1/7 - a <= 1/7 - 3/28 = 1/28 < 5/84 . thus, in an optimal partition, each 1/4 is split into 3 or 4 parts. if some 1/7 is split into 3 or more parts, then the mesh is <= 1/21 < 5/84 . if some 1/7 is not split, then it must occur as a part of some 1/4 . as above, this 1/4 must be split into at least 3 parts, so one of the other parts is at most (1/4 - 1/7) / 2 = 3/56 < 5/84 . thus, in an optimal partition, each 1/7 is split into exactly 2 parts. therefore, there are exactly 14 parts, and 2 of the 1/4 's are split into 3 parts, and the other 2 split into 4 parts. consider a 1/4 that is split into 3 parts. we then have 1/4 = a + b + c , where a <= b <= c , so c >= 1/12 . this occurs as a part of 1/7 , so the other part is 1/7 - c <= 5/84 . this proves that the mesh is at most 5/84 in all cases. moreover, if the mesh is indeed 5/84 , then the 1/4 's that are split into 3 parts must both split as 1/12 + 1/12 + 1/12 . each of these six 1/12 's must be part of 1/7 , which each split as 1/12 + 5/84 . so now there are six parts of 5/84 , and this shows that the two 1/4 's that split into 4 parts must both split as 5/84 + 5/84 + 5/84 + 1/14 . this proves that the partition is the same as rich's. mike
I used "divide and concur" to get lower bounds for the muffin problem. My normalization convention is yet different from the previous ones. Consider a solution for the case m = 8, n = 9: 0, 0, 4, 0, 0, 0, 0, 5, 0 0, 4, 0, 0, 0, 0, 5, 0, 0 0, 0, 0, 0, 3, 3, 3, 0, 0 0, 4, 0, 5, 0, 0, 0, 0, 0 4, 0, 0, 0, 5, 0, 0, 0, 0 0, 0, 4, 0, 0, 5, 0, 0, 0 4, 0, 0, 0, 0, 0, 0, 0, 5 0, 0, 0, 3, 0, 0, 0, 3, 3 Each of the 8 rows sums to 9 and each of the 9 columns sums to 8. The optimization problem is to maximize the smallest non-zero array element. I'll call this number U(m,n). The array above shows U(8, 9)
= 3.
Here are my lower bounds for U(m, n): 1 2 3 4 5 6 7 8 9 1 1 2 1 2 3 1 1 3 4 1 2 1 4 5 1 1 5/4 3/2 5 6 1 2 3 2 2 6 7 1 1 5/4 5/3 5/3 2 7 8 1 2 4/3 4 2 2 9/4 8 9 1 1 3 7/4 2 3 5/2 3 9 The entry in column 4 row 7 is the bound on U(4, 7), which in fact equals the optimum value that was the subject of previous posts ( U(m, n) = m n T (m, n) ). I suspect several of my bounds are optimal values. I'm happy to supply the partitions to anyone interested. Anyone with access to an industrial grade linear programming package might be able to prove upper bounds. The feasibility problem, that a solution exists with U(m, n) = u, can be formulated as a mixed-integer programming problem. There are m*n real variables x_{ij} that correspond to the array elements in my table above. These are positive and have the equality constraints on row and column sums (rows sum to n, columns to m). In addition, there are m*n binary variables y_{ij} that encode the positions of the zeroes. The two types of variables are constrained by a pair of inequalities: y_{ij} u <= x_{ij} x_{ij} <= b y_{ij} where b is a convenient upper bound on all the x_{ij} (we can always use b = min(m, n)). This is just a widget for imposing x_{ij} = 0 OR u <= x_{ij} <= b. These seem like very difficult linear programs: I was unable to go beyond (m, n) = (4, 7) with the freeware program lpsolve. Veit On Jan 9, 2009, at 1:35 AM, Michael Reid wrote:
i'll do it in the framework of partitions of 1 . define the mesh of a partition to be its smallest part. rich's partition is 5/84 + 5/84 + 5/84 + 5/84 + 5/84 + 5/84 + 1/14 + 1/14 + 1/12 + 1/12 + 1/12 + 1/12 + 1/12 + 1/12 , which has mesh 5/84 , and is simultaneously a refinement of 1/4 + 1/4 + 1/4 + 1/4 and of 1/7 + 1/7 + 1/7 + 1/7 + 1/7 + 1/7 + 1/7 .
if some 1/4 is split into 5 or more parts, then the mesh is <= 1/20 < 5/84 .
since 1/4 cannot be a part of 1/7 , each 1/4 must be split into at least 2 parts. suppose some 1/4 is split into exactly 2 parts, say 1/4 = a + b , where a <= b . we have 1/8 <= b <= 1/7 , so 3/28 <= a <= 1/8 . now a occurs as a part of 1/7 , so it has another part at most 1/7 - a <= 1/7 - 3/28 = 1/28 < 5/84 .
thus, in an optimal partition, each 1/4 is split into 3 or 4 parts.
if some 1/7 is split into 3 or more parts, then the mesh is <= 1/21 < 5/84 .
if some 1/7 is not split, then it must occur as a part of some 1/4 . as above, this 1/4 must be split into at least 3 parts, so one of the other parts is at most (1/4 - 1/7) / 2 = 3/56 < 5/84 .
thus, in an optimal partition, each 1/7 is split into exactly 2 parts. therefore, there are exactly 14 parts, and 2 of the 1/4 's are split into 3 parts, and the other 2 split into 4 parts. consider a 1/4 that is split into 3 parts. we then have 1/4 = a + b + c , where a <= b <= c , so c >= 1/12 . this occurs as a part of 1/7 , so the other part is 1/7 - c <= 5/84 . this proves that the mesh is at most 5/84 in all cases.
moreover, if the mesh is indeed 5/84 , then the 1/4 's that are split into 3 parts must both split as 1/12 + 1/12 + 1/12 . each of these six 1/12 's must be part of 1/7 , which each split as 1/12 + 5/84 . so now there are six parts of 5/84 , and this shows that the two 1/4 's that split into 4 parts must both split as 5/84 + 5/84 + 5/84 + 1/14 . this proves that the partition is the same as rich's.
mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Michael Reid -
Veit Elser