Re: [math-fun] muffin problem
I've calcuated U(4,13) = 11/6 (using Veit's notation) using CPLEX (industrial strength MIP) with the MIP that Veit suggested.
i can now determine T(4, n) in general. recall that my normalization is that T(m, n) equals the maximum c such that there is a partition of 1 with all parts >= c , which is simultaneously a refinement of 1/m + 1/m + ... + 1/m = 1 and also of 1/n + 1/n + ... + 1/n = 1 . T(4, 4n) = 1/4n , with unique partition 4n * 1/(4n) . this is obvious. T(4, 4n+2) = 1/(8n+4) . 4 * [(2n+1) * 1/(8n+4)] <---> (4n+2) * [1/(8n+4) + 1/(8n+4)] achieves this bound. moreover, at least one 1/(4n+2) must be split, so it has a part at most 1/(8n+4) . the partition is not unique; at least two 1/(4n+2) 's must split into 1/(8n+4) + 1/(8n+4) . the others either split in the same way, or do not split. T(4, 2n+1) = (2n-1)/(4n(2n+1)) if n >= 1 . the case n = 1 is T(4, 3) = T(3, 4) = 1/12 , which is easy to handle separately. if n > 1 , there is a unique optimal partition, which is 2 * [n * (2n-1)/(4n(2n+1)) + 1/(4n+2)] + 2 * [n * 1/(4n)] <---> 2n * [(2n-1)/(4n(2n+1)) + 1/(4n)] + [1/(4n+2) + 1/(4n+2)] suppose that 1/4 splits as 1/(2n+1) + 1/(2n+1) + ... + 1/(2n+1) + ( p smaller parts ) , where there are k > 0 parts of size 1/(2n+1) . if p >= n - 2k + 1 , then the smallest of the parts is at most (1/4 - k/(2n+1))/p <= ((2n-4k+1)/(4(2n+1)))/(n - 2k + 1) = (2 - 1/(n - 2k + 1))/(4(2n+1)) < (2 - 1/n)/(4(2n+1)) = (2n-1)/(4n(2n+1)) , so this part is too small. on the other hand, if p <= n - 2k , then the largest of the parts not equal to 1/(2n+1) is at least (1/4 - k/(2n+1))/p . since this occurs as a part of 1/(2n+1) , it has another part at most 1/(2n+1) - (1/4 - k/(2n+1))/p <= 1/(2n+1) - (1/4 - k/(2n+1))/(n - 2k) = (2 - 1/(n - 2k))/(4n(2n+1)) < (2 - 1/n)/(4(2n+1)) = (2n-1)/(4n(2n+1)) , so again there is a part which is too small. this shows that no 1/4 can contain any parts of size 1/(2n+1) , and therefore every 1/(2n+1) must split. now suppose that 1/4 splits into p parts, which we know must all be less than 1/(2n+1) . if p >= n+2 , then the smallest of these parts is <= 1/(4(n+2)) < (2n-1)/(4n(2n+1)) , so too small. (here we need n > 1 .) if p <= n-1 , then the largest of these parts is at least 1/(4(n-1)) , and since it occurs as part of 1/(2n+1) , there must be another part of size <= 1/(2n+1) - 1/(4(n-1)) < (2n-1)/(4n(2n+1)) , which is again too small. therefore, each 1/4 splits into either n or n+1 parts. if 1/(2n+1) splits into 3 or more parts, then some part has size <= 1/(3(2n+1)) , which is less than (2n-1)/(4n(2n+1)) if n > 1 . thus each 1/(2n+1) splits into exactly 2 parts, so there are 4n+2 parts in total. now two of the 1/4 's must split into n parts, and the other two must split into n+1 parts. moreover, the largest part in either of the 1/4 's that split into n parts has size >= 1/(4n) . since it occurs as part of 1/(2n+1) , the other part has size <= 1/(2n+1) - 1/(4n) = (2n-1)/(4n(2n+1)) . thus, to have optimality, both of the 1/4 's that split into 1/(4n) + 1/(4n) + ... + 1/(4n) , and now n of the 1/(2n+1) 's must split as (2n-1)/(4n(2n+1)) + 1/(4n) . finally, there are 2n parts of the minimal size (2n-1)/(4n(2n+1)) , and neither of the remaining 1/4 's can contain n+1 of them , so both contain n of them, and thus split as n * (2n-1)/(4n(2n+1)) + 1/(4n+2) , which determines the partition. T(1, n) and T(2, n) are very easy to determine in general. it looks like there is probably also pattern in T(3, n) . T(6, n) might also be possible to determine in general. mike
T(1, n) and T(2, n) are very easy to determine in general. it looks like there is probably also pattern in T(3, n) .
apparently U(3,3n) = 3 and U(3,3n +/- 1) = (3n-1)/2n. this translates to T(3,3n) = 1/3n, T(3,3n-1) = 1/6n, and T(3,3n+1) = (3n-1)/6n(n+1). got a proof mike? :) erich
Hi muffin choppers, I've been thinking about the muffin problem, too, though I've only just read most of the posts, since I wanted to work things out for myself. Before I talk specifics, I'll say say that I'm using Veit's U(m, n) notation (with each muffin having size n, which is the same as looking at a partition of mn that refines both mn = m + m + ... + m and mn = n + n + ... + n). I agree that, from a mathematical point of view, Mike Reid's T(m, n) is more natural, but it makes the denominators much bigger and seems to needlessly complicate the arguments. And I don't like the asymmetry of S(m, p). Also, I'll point out that U(m, n, p), for instance, can be viewed as a partition of mnp. Another thing, I don't like Scott's "piece optimal" or "ratio optimal" as secondary objectives, since they're sort of ad hoc and still don't give a unique optimum. I figure that, since the primary objective is to maximize the size of the smallest piece, the next objective should be to maximize the size of the second smallest piece, and so on. That is, I want the lexically largest multiset of pieces, when arranged in increasing order. Then there is always a unique optimal set of pieces. Finally, I prefer to write multiplicities _after_ parts, so I write "(1/2) * 2" to mean two parts of size 1/2. Now I came up with essentially the same arguments for computing U(3, 3k+-1) that Mike Reid did (for T), but I have a much simpler proof for T(4, 2k+1) = (2k-1)/k (with k>=1) than his: Recall that we want a corefinement of 4 * (2k+1) and (2k+1) * 4. We have the partition 4(2k+1) = (2k-1)/k * 2k + 2 * 2 + (2k+1)/k * 2k, which we want to prove is optimal (in my strong sense above). We may assume k>=2, since the case k=1 is easy. Then U(4, 2k+1) >= (2k-1)/k > 4/3, so no 4 can be divided into more than two pieces, which means that there are at most 2(2k+1) pieces. Then one of the four 2k+1's must be divided into at most (2k+1)/2 pieces, meaning at most k, one of which has size at least (2k+1)/k. This piece is part of a 4, so the other part of that 4 has size at most 4 - (2k+1)/k = (2k-1)/k, which proves U(4, 2k+1) = (2k-1)/k. Now for the optimal solution, we must have equality, which means that 2k+1 is divided into exactly k pieces, which means a second 2k+1 is divided into k equal pieces. So now we are forced to have (2k-1)/k * 2k and (2k+1)/k * 2k, with the latter bunch the constituents of two of the 2k+1's. Now these account for 8k of the total 8k+4, so the best possibilies for the rest would be 4 or 2 * 2. In either case, these pieces have integer sizes, so when making the other two 2k+1's, we have to use k of the (2k-1)/k's at a time, giving 2k-1. Then we can't use the 4, so 2 * 2 is optimal, proving the result. I think I have the optimal partition for all cases of (m, m+1), and I have calculated optimal partitions for many of the values of U(m, n) given earlier, but I'll give those later. David P. Moulton
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
Hi muffin masticators, I now have a proof of an asymptotic result I'd conjectured a while ago. Recall that I write multiplicities after parts and that I'm working with U(m, n), the size of the smallest part in a common refinement of m * n and n * m. Theorem: Given m, the limit, as n goes to infinity over nonmultiples of m, of U(m, n) is m/2. Note that for m not dividing n, we always have U(m, n) <= m/2, since some m must be split, so we just have to prove that the lim inf of U(m, n) over all n is at least m/2. Lemma 1: Given m>=3, let e be 1 if m is odd and 2 if m is even. For k>=1 we have U(m, (km-1)(m-e)/2) >= (km-1)/2k = m/2 - 1/2k. Proof of Lemma 1: We use the multiset (m/2 - 1/2k) * ek(m-e), m/2 * (km-2ek-1)(m-e), (m/2 + 1/2k) * ek(m-e). It is clear that the smallest part has the desired size and that the parts can be paired up to give (km-1)(m-e)/2 copies of m. Also, all the smallest parts can be added together to give e copies of (km-1)(m-e)/2. Finally, we have m/2 * (km-2ek-1) + (m/2 + 1/2k) * ek = km^2/2 - ekm/2 - m/2 + e/2 = (km-1)(m-e)/2, so the rest of the pieces can be combined to make m-e more copies of (km-1)(m-e)/2, and this is a valid common refinement. QED In fact, it's not too hard to show that if we combine as many pairs of m/2's as possible into m's, then we get the optimum partition in my sense of lexically maximizing the increasing list of pieces sizes. In particular, we get equality on U, although this is not needed for the proof of the theorem. Lemma 2: For all positive m, n_1, n_2, ..., n_k we have U(m, n_1 + ... + n_k) >= min_i { U(m, n_i) }. Proof of Lemma 2: Take the union of the optimal partitions for each pair (m, n_i). Together they give m * (n_1 + ... + n_k), and we can combine the n_i * m 's to give (n_1 + ... + n_k) * m. Thus we have a corefinement of m * (n_1 + ... + n_k) and (n_1 + ... + n_k) * m with smallest part equal to min_i { U(m, n_i) }. QED Proof of Theorem: The result is vacuous for m=1 and trivial for m=2, so take m>=3 and define e as in Lemma 1. First, we have U(m, m/e) >= m/2. Now fix k and note that m/e and (km-1)(m-e)/2 are relatively prime. Then for every sufficiently large integer n we can write n = m/e * a + (km-1)(m-e)/2 * b with a,b>=0, and we have U(m, n) = U(m, m/e * a + (km-1)(m-e)/2 * b) >= min( U(m, m/e), U(m, (km-1)(m-e)/2) ) by Lemma 2 >= m/2 - 1/2k. Letting k go to infinity now proves the theorem. QED David P. Moulton
Hi Muffinisectors, There's a general upper bound for the muffin problem that, while implicit in other people's posts, has not been explicitly stated, so I record it here. Recall that U(m, n) is the largest size of the smallest part in a common refinement of the partitions m * n and n * m. I'll use square brackets for the floor function. Proposition. For m and n with m not dividing 2n we have U(m, n) <= max( m/3, min( n/([2n/m]+1), m - n/[2n/m] ) ). Proof. Take a partition achieving U(m, n). If some m is divided into at least 3 parts, the smallest of these is at most m/3, and we are done. So we may assume that every m is divided into at most 2 parts, and we need to show that the smallest piece of the refining partition is bounded above by both expressions inside the "min". Since m does not divide n, at least one m is divided into 2 parts, one of which has size at most m/2, so we may split all undivided m's into 2 equal parts without reducing the size of the smallest piece. Then each of the m's is divided into exactly 2 pieces. Since there are n of them, there are exactly 2n pieces in the partition. Now the m n's get divided into 2n pieces, and since m does not divide 2n, some n is divided into at least [2n/m]+1 pieces, and some other n is divided into at most [2n/m] pieces. The smallest of these pieces has size at most n/([2n/m]+1), which proves the first of the two bounds, and the largest of the pieces has size at least n/[2n/m]. But then consider the m that has this last piece as a constituent. It has at least one other piece, and this other piece has size at most m - n/[2n/m], which finishes the proof. QED Now this is interesting mainly for m < n, which we can assume by symmetry, and then you can work out that we always have m/3 < n/([2n/m]+1), and we have m/3 >= m - n/[2n/m] exactly for 4m/3 <= n < 3m/2. Thus we can restate the proposition more conveniently: 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. David P. Moulton
Earlier today I wrote
There's a general upper bound for the muffin problem that, while implicit in other people's posts, has not been explicitly stated, so I record it here.
...
I apologize for this claim--the corollary I gave is basically equivalent to the "fit constraint" upper bound Scott Huddleston gave in his post of January 20. David P. Moulton
Do all these muffin results justify a paper? Are they being collected anywhere? ----- Original Message ----- From: "David P. Moulton" <moulton@idaccr.org> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, February 19, 2009 1:38 PM Subject: Re: [math-fun] a general muffin problem upper bound
Earlier today I wrote
There's a general upper bound for the muffin problem that, while implicit in other people's posts, has not been explicitly stated, so I record it here.
...
I apologize for this claim--the corollary I gave is basically equivalent to the "fit constraint" upper bound Scott Huddleston gave in his post of January 20.
David P. Moulton
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-------------------------------------------------------------------------------- No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.0.237 / Virus Database: 270.11.1/1962 - Release Date: 02/20/09 07:26:00
If there is something coherent to say on the subject, I'd like to suggest (putting on my editor's hat) the Entertainments part of the Mathematical Intelligencer... --Michael On Fri, Feb 20, 2009 at 8:04 AM, David Wilson <davidwwilson@comcast.net>wrote:
Do all these muffin results justify a paper?
Are they being collected anywhere?
----- Original Message ----- From: "David P. Moulton" <moulton@idaccr.org> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, February 19, 2009 1:38 PM Subject: Re: [math-fun] a general muffin problem upper bound
Earlier today I wrote
There's a general upper bound for the muffin problem that, while implicit in other people's posts, has not been explicitly stated, so I record it here.
...
I apologize for this claim--the corollary I gave is basically equivalent to the "fit constraint" upper bound Scott Huddleston gave in his post of January 20.
David P. Moulton
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--------------------------------------------------------------------------------
No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.0.237 / Virus Database: 270.11.1/1962 - Release Date: 02/20/09 07:26:00
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
On Fri, 16 Jan 2009, Michael Reid wrote:
i can now determine T(4, n) in general....
T(1, n) and T(2, n) are very easy to determine in general. it looks like there is probably also pattern in T(3, n) . T(6, n) might also be possible to determine in general.
Okay, it turns out U(6, n) wasn't very hard, and I got around to going through it the other day. We can assume n is relatively prime to 6, since otherwise you can multiply up a solution for U(2, n/3) or U(3, n/2), and it's still optimal. We already have optimal partitions for U(5, 6) and U(6, 7). Here are the rest; I decided to write mixed fractions, since that's how I think of them, and then I can use "-+" to mean take the parts using the "-" and also take the parts using the "+" (so there are five part sizes for each partition). Here they are U(6, 6k-1): [3 -+ 2/(2k-1)] * (4k-2), [3 -+ 1/k(2k-1)] * 2k, 3 * 2 (k >= 2) U(6, 6k+1): [3 -+ 2/(2k+1)] * (4k+2), [3 -+ 1/(k-1)(2k+1)] * (2k-2), 3 * 2 (k >= 2) One can check that they are valid co-refinements, and the standard upper bound shows that they achieve U. And a bit more checking shows that they are optimal partitions. David P. Moulton
On Thu, 5 Mar 2009, I wrote:
Okay, it turns out U(6, n) wasn't very hard, and I got around to going through it the other day.
I skipped over U(5, n), since there were several cases, but I went through them, and it's not so bad. In general, when considering U(m, n), you have to think about 2n mod m, but then sometimes you have to look at cases based on (roughly) the number of pieces an n splits into, modulo 2n mod m. Anyway, for n>=3m/2 (n>=8) (and n not a multiple of 5), the values for U(5, n) all achieve equality in the general upper bound U(m, n) <= min( n/([2n/m]+1), m - n/[2n/m] ), except for the case U(5, 11)=13/6, which I discussed earlier. Here are the optimal partitions for n at least 5 and not 7 or 11. I write them with mixed fractions, and I use "-+" to mean that the indicated number of pieces occur both with the "-" sign and with the "+" sign. Also, for a half an odd integer, I write m * a to mean m/2 * 1, m * (a-1/2). Then, whether a is integral or not, I'll write (m * a)b to mean b copies of m * a. Finally, I write e for either -1 or +1. These are all optimal for k>=1 with the exceptions of (5, 7) (for which you can do better) and (5, 11) (for which the construction doesn't work). U(5, 5k): 5 * 5k U(5, 10k+2e): [5/2 -+ 1/2k] * 4k, (5 * (3k+e)/2)4 U(5, 10k+3e): [5/2 -+ 1/(2k+e)] * (4k+2e), [5/2 -+ 1/(2k+e)(6k-1+e)] * (6k-1+e), 5/2 * 2 U(5, 15k+e): [5/2 -+ 3/(12k+2e)] * (12k+2e), [5/2 -+ 1/(12k+2e)k] * 2k, (5 * (k-e)/2)2 U(5, 15k+4e): [5/2 -+ 3/(12k+2e)] * (12k+2e), [5/2 -+ 1/(12k+2e)(k+e)] * (2k+2e), (5 * k/2)2 U(5, 15k+6e): [5/2 -+ 1/(4k+2e)] * (12k+6e), 5 * 3k As usual, one can check that these are valid co-refinements of 5 * n and n * 5, and the standard upper bound above shows that they achieve U. And a bit more checking shows that they are optimal partitions. Presumably, for any fixed value of m, one can proceed in this manner, but there will probably be more cases and more exceptions for small values of n. David P. Moulton
I decided that the one other value of m that it wouldn't be so bad to deal with is 8, so now I'll give lexically optimal partitions for U(8, n). As usual, for even values of n, the optimal partitions are obtained by taking those for U(4, n/2) and doubling all piece sizes and multiplicities. Here are the optimal partitions for odd n>=9. They all achieve equality in the usual upper bound U(m, n) <= min( n/([2n/m]+1), m - n/[2n/m] ), except for n=11, when the bound doesn't apply, and you can do better. For n=11, 17, the general constructions don't work, and I do them separately. I (usually) write parts with mixed fractions, and I use "-+" to mean that the indicated number of pieces occur both with the "-" sign and with the "+" sign. Also, I write e for either -1 or +1. (8, 11): 8/3 * 6, 11/3 * 6, 4 * 6, 13/3 * 6 (8, 17): 17/5 * 10, 19/5 * 2, 39/10 * 4, 4 * 2, 41/10 * 4, 21/5 * 2, 23/5 * 10 (8, 12k+e): [4 -+ 3/(3k+e)] * (6k+2e), [4 -+ 2/(2k-e)(3k+e)] * (4k-2e), [4 -+ 2/(2k-1+e)(2k-e)(3k+e)] * (2k-1+e), 4 * 2 (8, 12k+3e): [4 -+ 1/k] * 6k, 4 * 6, 8 * (6k-3+3e) (8, 12k+5e): [4 -+ 3/(3k+2e)] * (6k+4e), [4 -+ 2/(2k+e)(3k+2e)] * (4k+2e), [4 -+ 2/(2k-1-e)(2k+e)(3k+2e)] * (2k-1-e), 4 * 2 David P. Moulton
participants (5)
-
David P. Moulton -
David Wilson -
Erich Friedman -
Michael Kleber -
Michael Reid