Re: [math-fun] muffin problem
several more values, to cover your table: T(7, 8) = 5/112 ; 4 * 5/112 + 2 * 3/56 + 4 * 1/16 + 2 * 1/14 + 4 * 9/112 T(7, 9) = 5/125 ; 6 * 5/126 + 3 * 1/21 + 3 * 4/63 + 6 * 1/14 T(8, 9) = 1/24 ; 6 * 1/24 + 6 * 1/18 + 6 * 5/72 the latter two agree with your table; but the first gives an improvement. (no contradiction, since you only gave a lower bound.) mike
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.
i've also "calculated" some values. recall that my T(m, n) is the maximum c such that there exists a partition of 1 with each part
= c , and which is a simultaneous refinement of 1/m + 1/m + ... + 1/m = 1 and of 1/n + 1/n + ... = 1/n = 1 .
i believe i have a valid proof for each of the values below. i also give one such partition for each; showing that it's a refinement is easy.
T(m, n) = 1/n if m divides n ; n * 1/n
T(2, 2n+1) = 1/(2(2n+1)) ; (4n+2) * 1/(2(2n+1))
T(3, 4) = 1/12 ; 12 * 1/12 T(3, 5) = 1/12 ; 4 * 1/12 + 2 * 1/10 + 4 * 7/60 T(3, 7) = 5/84 ; 4 * 5/84 + 6 * 1/14 + 4 * 1/12 T(3, 8) = 1/18 ; 6 * 1/18 + 6 * 5/72 + 2 * 1/8 T(3, 10) = 2/45 ; 6 * 2/45 + 6 * 1/18 + 2 * 1/10 T(3, 11) = 1/24 ; 8 * 1/24 + 2 * 1/22 + 8 * 13/264 + 2 * 1/11 T(3, 13) = 11/312 ; 8 * 11/312 + 2 * 1/26 + 8 * 1/24 + 4 * 1/13
T(4, 5) = 3/40 ; 4 * 3/40 + 2 * 1/10 + 4 * 1/8 T(4, 6) = 1/12 ; 12 * 1/12 T(4, 7) = 5/84 ; 6 * 5/84 + 2 * 1/14 + 6 * 1/12 T(4, 9) = 7/144 ; 8 * 7/144 + 2 * 1/18 + 8 * 1/16 T(4, 10) = 1/20 ; 20 * 1/20 T(4, 11) = 9/220 ; 10 * 9/220 + 2 * 1/22 + 10 * 1/20 T(4, 4n+2) = 1/(2(4n+2)) ; (8n+4) * 1/(2(4n+2))
T(5, 6) = 1/15 ; 6 * 1/15 + 6 * 1/10 T(5, 7) = 1/21 ; 3 * 1/21 + 6 * 1/15 + 6 * 8/105 T(5, 8) = 1/20 ; 4 * 1/20 + 4 * 3/40 + 4 * 1/8 T(5, 9) = 2/45 ; 6 * 2/45 + 6 * 1/15 + 3 * 1/9
T(6, 7) = 1/21 ; 12 * 1/21 + 6 * 1/14 T(6, 8) = 1/24 ; 24 * 1/24 T(6, 9) = 1/18 ; 18 * 1/18
these appear to agree with your lower bounds on the overlap.
mike
Thanks for the improvement! Here's a general upper bound for the case 1 < n/m < = 3/2: I'm going to use my normalization -- your fractions are driving me crazy! Recall that we seek arrays with m rows, n columns, such that all row sums equal n and all column sums equal m. We want an upper bound on U(m, n), the smallest non-zero entry. Let p be the average number of non-zeroes per row, q the average number of non-zeroes per column. Since m < n, we have q < p. First suppose that there is a column with only one non-zero; its value will be m. Look in the same row (of that non-zero) and there must be some other non-zeroes, since the row sum n is greater than m. An upper bound on this other non-zero is U(m, n) <= n - m <= n - 2/3n = n/3. Now suppose none of the columns have a single non-zero. Then q >= 2, and so p > 2. That tells us that some row has at least three non-zeroes from which we get the bound U(m, n) <= n/3. Five entries in my table actually achieve this bound. Veit On Jan 12, 2009, at 11:25 PM, Michael Reid wrote:
several more values, to cover your table:
T(7, 8) = 5/112 ; 4 * 5/112 + 2 * 3/56 + 4 * 1/16 + 2 * 1/14 + 4 * 9/112 T(7, 9) = 5/125 ; 6 * 5/126 + 3 * 1/21 + 3 * 4/63 + 6 * 1/14 T(8, 9) = 1/24 ; 6 * 1/24 + 6 * 1/18 + 6 * 5/72
the latter two agree with your table; but the first gives an improvement. (no contradiction, since you only gave a lower bound.)
mike
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.
i've also "calculated" some values. recall that my T(m, n) is the maximum c such that there exists a partition of 1 with each part
= c , and which is a simultaneous refinement of 1/m + 1/m + ... + 1/m = 1 and of 1/n + 1/n + ... = 1/n = 1 .
i believe i have a valid proof for each of the values below. i also give one such partition for each; showing that it's a refinement is easy.
T(m, n) = 1/n if m divides n ; n * 1/n
T(2, 2n+1) = 1/(2(2n+1)) ; (4n+2) * 1/(2(2n+1))
T(3, 4) = 1/12 ; 12 * 1/12 T(3, 5) = 1/12 ; 4 * 1/12 + 2 * 1/10 + 4 * 7/60 T(3, 7) = 5/84 ; 4 * 5/84 + 6 * 1/14 + 4 * 1/12 T(3, 8) = 1/18 ; 6 * 1/18 + 6 * 5/72 + 2 * 1/8 T(3, 10) = 2/45 ; 6 * 2/45 + 6 * 1/18 + 2 * 1/10 T(3, 11) = 1/24 ; 8 * 1/24 + 2 * 1/22 + 8 * 13/264 + 2 * 1/11 T(3, 13) = 11/312 ; 8 * 11/312 + 2 * 1/26 + 8 * 1/24 + 4 * 1/13
T(4, 5) = 3/40 ; 4 * 3/40 + 2 * 1/10 + 4 * 1/8 T(4, 6) = 1/12 ; 12 * 1/12 T(4, 7) = 5/84 ; 6 * 5/84 + 2 * 1/14 + 6 * 1/12 T(4, 9) = 7/144 ; 8 * 7/144 + 2 * 1/18 + 8 * 1/16 T(4, 10) = 1/20 ; 20 * 1/20 T(4, 11) = 9/220 ; 10 * 9/220 + 2 * 1/22 + 10 * 1/20 T(4, 4n+2) = 1/(2(4n+2)) ; (8n+4) * 1/(2(4n+2))
T(5, 6) = 1/15 ; 6 * 1/15 + 6 * 1/10 T(5, 7) = 1/21 ; 3 * 1/21 + 6 * 1/15 + 6 * 8/105 T(5, 8) = 1/20 ; 4 * 1/20 + 4 * 3/40 + 4 * 1/8 T(5, 9) = 2/45 ; 6 * 2/45 + 6 * 1/15 + 3 * 1/9
T(6, 7) = 1/21 ; 12 * 1/21 + 6 * 1/14 T(6, 8) = 1/24 ; 24 * 1/24 T(6, 9) = 1/18 ; 18 * 1/18
these appear to agree with your lower bounds on the overlap.
mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I've calcuated U(4,13) = 11/6 (using Veit's notation) using CPLEX (industrial strength MIP) with the MIP that Veit suggested. It seems to be implicit in the above discussion that the optimal values of U(m,n) are all rational. Perhaps this seems obvious, but here's a proof (courtesy of David Moulton): For each of the 2^mn settings of the y[i,j] variables (i.e. y[i,j] = 1, if and only if x[i,j] > 0) we can find the optimal value by means of a linear program: maximize u subject to x[i,j] >= u for all i,j such that y[i,j] = 1, plus the column and row sums being the right value. All the coefficients of the resulting matrix are integers, so the vertices of the resulting polytope are rational. Can one put a good bound on the possible denominators? They all appear to be small. Victor On Mon, Jan 12, 2009 at 11:25 PM, Michael Reid <reid@gauss.math.ucf.edu> wrote:
several more values, to cover your table:
T(7, 8) = 5/112 ; 4 * 5/112 + 2 * 3/56 + 4 * 1/16 + 2 * 1/14 + 4 * 9/112 T(7, 9) = 5/125 ; 6 * 5/126 + 3 * 1/21 + 3 * 4/63 + 6 * 1/14 T(8, 9) = 1/24 ; 6 * 1/24 + 6 * 1/18 + 6 * 5/72
the latter two agree with your table; but the first gives an improvement. (no contradiction, since you only gave a lower bound.)
mike
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.
i've also "calculated" some values. recall that my T(m, n) is the maximum c such that there exists a partition of 1 with each part
= c , and which is a simultaneous refinement of 1/m + 1/m + ... + 1/m = 1 and of 1/n + 1/n + ... = 1/n = 1 .
i believe i have a valid proof for each of the values below. i also give one such partition for each; showing that it's a refinement is easy.
T(m, n) = 1/n if m divides n ; n * 1/n
T(2, 2n+1) = 1/(2(2n+1)) ; (4n+2) * 1/(2(2n+1))
T(3, 4) = 1/12 ; 12 * 1/12 T(3, 5) = 1/12 ; 4 * 1/12 + 2 * 1/10 + 4 * 7/60 T(3, 7) = 5/84 ; 4 * 5/84 + 6 * 1/14 + 4 * 1/12 T(3, 8) = 1/18 ; 6 * 1/18 + 6 * 5/72 + 2 * 1/8 T(3, 10) = 2/45 ; 6 * 2/45 + 6 * 1/18 + 2 * 1/10 T(3, 11) = 1/24 ; 8 * 1/24 + 2 * 1/22 + 8 * 13/264 + 2 * 1/11 T(3, 13) = 11/312 ; 8 * 11/312 + 2 * 1/26 + 8 * 1/24 + 4 * 1/13
T(4, 5) = 3/40 ; 4 * 3/40 + 2 * 1/10 + 4 * 1/8 T(4, 6) = 1/12 ; 12 * 1/12 T(4, 7) = 5/84 ; 6 * 5/84 + 2 * 1/14 + 6 * 1/12 T(4, 9) = 7/144 ; 8 * 7/144 + 2 * 1/18 + 8 * 1/16 T(4, 10) = 1/20 ; 20 * 1/20 T(4, 11) = 9/220 ; 10 * 9/220 + 2 * 1/22 + 10 * 1/20 T(4, 4n+2) = 1/(2(4n+2)) ; (8n+4) * 1/(2(4n+2))
T(5, 6) = 1/15 ; 6 * 1/15 + 6 * 1/10 T(5, 7) = 1/21 ; 3 * 1/21 + 6 * 1/15 + 6 * 8/105 T(5, 8) = 1/20 ; 4 * 1/20 + 4 * 3/40 + 4 * 1/8 T(5, 9) = 2/45 ; 6 * 2/45 + 6 * 1/15 + 3 * 1/9
T(6, 7) = 1/21 ; 12 * 1/21 + 6 * 1/14 T(6, 8) = 1/24 ; 24 * 1/24 T(6, 9) = 1/18 ; 18 * 1/18
these appear to agree with your lower bounds on the overlap.
mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Two questions ... Do we know that numbers that are not relatively prime can be reduced? I.e., is the answer for 6,4 the same as 3,2? If we have M muffins and P people, is the (a?) best answer for M+P muffins to give everyone 1 muffin and reduce to the M,P problem? Rich ------------ Quoting victor miller <victorsmiller@gmail.com>:
I've calcuated U(4,13) = 11/6 (using Veit's notation) using CPLEX (industrial strength MIP) with the MIP that Veit suggested.
It seems to be implicit in the above discussion that the optimal values of U(m,n) are all rational. Perhaps this seems obvious, but here's a proof (courtesy of David Moulton):
For each of the 2^mn settings of the y[i,j] variables (i.e. y[i,j] = 1, if and only if x[i,j] > 0) we can find the optimal value by means of a linear program:
maximize u subject to
x[i,j] >= u for all i,j such that y[i,j] = 1, plus the column and row sums being the right value. All the coefficients of the resulting matrix are integers, so the vertices of the resulting polytope are rational. Can one put a good bound on the possible denominators? They all appear to be small.
Victor
On Mon, Jan 12, 2009 at 11:25 PM, Michael Reid <reid@gauss.math.ucf.edu> wrote:
several more values, to cover your table:
T(7, 8) = 5/112 ; 4 * 5/112 + 2 * 3/56 + 4 * 1/16 + 2 * 1/14 + 4 * 9/112 T(7, 9) = 5/125 ; 6 * 5/126 + 3 * 1/21 + 3 * 4/63 + 6 * 1/14 T(8, 9) = 1/24 ; 6 * 1/24 + 6 * 1/18 + 6 * 5/72
the latter two agree with your table; but the first gives an improvement. (no contradiction, since you only gave a lower bound.)
mike
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.
i've also "calculated" some values. recall that my T(m, n) is the maximum c such that there exists a partition of 1 with each part
= c , and which is a simultaneous refinement of 1/m + 1/m + ... + 1/m = 1 and of 1/n + 1/n + ... = 1/n = 1 .
i believe i have a valid proof for each of the values below. i also give one such partition for each; showing that it's a refinement is easy.
T(m, n) = 1/n if m divides n ; n * 1/n
T(2, 2n+1) = 1/(2(2n+1)) ; (4n+2) * 1/(2(2n+1))
T(3, 4) = 1/12 ; 12 * 1/12 T(3, 5) = 1/12 ; 4 * 1/12 + 2 * 1/10 + 4 * 7/60 T(3, 7) = 5/84 ; 4 * 5/84 + 6 * 1/14 + 4 * 1/12 T(3, 8) = 1/18 ; 6 * 1/18 + 6 * 5/72 + 2 * 1/8 T(3, 10) = 2/45 ; 6 * 2/45 + 6 * 1/18 + 2 * 1/10 T(3, 11) = 1/24 ; 8 * 1/24 + 2 * 1/22 + 8 * 13/264 + 2 * 1/11 T(3, 13) = 11/312 ; 8 * 11/312 + 2 * 1/26 + 8 * 1/24 + 4 * 1/13
T(4, 5) = 3/40 ; 4 * 3/40 + 2 * 1/10 + 4 * 1/8 T(4, 6) = 1/12 ; 12 * 1/12 T(4, 7) = 5/84 ; 6 * 5/84 + 2 * 1/14 + 6 * 1/12 T(4, 9) = 7/144 ; 8 * 7/144 + 2 * 1/18 + 8 * 1/16 T(4, 10) = 1/20 ; 20 * 1/20 T(4, 11) = 9/220 ; 10 * 9/220 + 2 * 1/22 + 10 * 1/20 T(4, 4n+2) = 1/(2(4n+2)) ; (8n+4) * 1/(2(4n+2))
T(5, 6) = 1/15 ; 6 * 1/15 + 6 * 1/10 T(5, 7) = 1/21 ; 3 * 1/21 + 6 * 1/15 + 6 * 8/105 T(5, 8) = 1/20 ; 4 * 1/20 + 4 * 3/40 + 4 * 1/8 T(5, 9) = 2/45 ; 6 * 2/45 + 6 * 1/15 + 3 * 1/9
T(6, 7) = 1/21 ; 12 * 1/21 + 6 * 1/14 T(6, 8) = 1/24 ; 24 * 1/24 T(6, 9) = 1/18 ; 18 * 1/18
these appear to agree with your lower bounds on the overlap.
mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If we have M muffins and P people, is the (a?) best answer for M+P muffins to give everyone 1 muffin and reduce to the M,P problem?
Isn't the dual to the original problem (that is, dividing 7 muffins among 4 people) a counterexample to this? Andy
It's true that U(m+p, p) >= U(m, p) but you can't replace this with an equality. The smallest counterexample is U(2, 3) = 1 U(5, 3) = 5/4 The reduction you are thinking of has the partition 3 0 0 1 1 0 3 0 1 1 0 0 3 1 1 with minimal element 1. Here's the optimal partition 7/4 0 7/4 0 3/2 0 7/4 0 7/4 3/2 5/4 5/4 5/4 5/4 0 Veit On Jan 16, 2009, at 8:51 AM, Andy Latto wrote:
If we have M muffins and P people, is the (a?) best answer for M+P muffins to give everyone 1 muffin and reduce to the M,P problem?
Isn't the dual to the original problem (that is, dividing 7 muffins among 4 people) a counterexample to this?
Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Jan 15, 2009, at 4:17 PM, victor miller wrote:
I've calcuated U(4,13) = 11/6 (using Veit's notation) using CPLEX (industrial strength MIP) with the MIP that Veit suggested.
It seems to be implicit in the above discussion that the optimal values of U(m,n) are all rational. Perhaps this seems obvious, but here's a proof (courtesy of David Moulton):
For each of the 2^mn settings of the y[i,j] variables (i.e. y[i,j] = 1, if and only if x[i,j] > 0) we can find the optimal value by means of a linear program:
maximize u subject to
x[i,j] >= u for all i,j such that y[i,j] = 1, plus the column and row sums being the right value. All the coefficients of the resulting matrix are integers, so the vertices of the resulting polytope are rational. Can one put a good bound on the possible denominators? They all appear to be small.
Victor
I'm sure you realize these "baker's dozen" instances are particularly important for the people who perpetrated this puzzle! That's the smallest denominator I've seen. Maybe you can test the following. It's trivial to show that U(k m, k n) >= k U(m, n) but for all the cases I've looked at >= can be replaced by = . Can you find a counterexample? I use "divide and concur" to find the binary y's and then plug the result into this Mma function: muffinLP[m_, n_, y_] := LinearProgramming[-IdentityMatrix[m n + 1][[m n + 1]], Join[Map[Total[IdentityMatrix[m n + 1][[#]]] &, Join[Transpose[#], #] &[Partition[Range[m n], n]]], Table[If[y[[i]] == 0, IdentityMatrix[m n + 1][[i]], IdentityMatrix[m n + 1][[i]] - IdentityMatrix[m n + 1][[m n + 1]]], {i, m n}]], Join[Table[{m, 0}, {n}], Table[{n, 0}, {m}], Map[If[# == 0, {0, 0}, {0, 1}] &, y]] , Method -> Simplex] y = {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0}; Last[muffinLP[4, 13, y]] 11/6 "Method -> Simplex" option returns rational values. Veit
participants (5)
-
Andy Latto -
Michael Reid -
rcs＠xmission.com -
Veit Elser -
victor miller