Maximizing the Product of Partition ElementsDate: 08/20/99 at 06:26:07 From: TJ Subject: Partitions Can you tell me how to begin trying to prove that the product of the elements in a partition is a maximum when the elements are equal? Date: 08/20/99 at 08:04:01 From: Doctor Anthony Subject: Re: Partitions In its simplest form consider that the number N is partitioned into two parts x and y, where x+y = N. y = N-x The product xy = x(N-x) P = Nx - x^2 and this is a parabola with a maximum point given by dP/dx = 0. dP/dx = N - 2x = 0 2x = N x = N/2 and y = N - N/2 = N/2 and so the product is a maximum if x = y = N/2. Another way of looking at the problem is to consider the arithmetic and geometric means, and to show that the geometric mean is a maximum when all the partitions of the number N are equal. Starting with numbers a and b: A = arithmetic mean = (a+b)/2 G = geometric mean = sqrt(ab) A - G = (a+b)/2 - sqrt(ab) = (a - 2sqrt(ab) + b)/2 [sqrt(a) - sqrt(b)]^2 = --------------------- 2 > 0 so A > G. In the case of n numbers a, b, c, ... the proof is by changing the numbers in such a way that A remains constant, but G gets larger until all the numbers are equal, at which point the arithmetic and geometric mean are equal. It follows that the original G must have been less than A. Suppose that in the set a, b, c, ... a > any other number and b < any other number. so a > A > b Now replace a by A and b by b' where b' = a+b-A (which is > 0) The new set of numbers is now A, b', c, ... A+b' = a+b so the sum of the set is unchanged and mean is unchanged. Ab' - ab = A(a+b-A) - ab = Aa + Ab - A^2 - ab = Aa - ab - A^2 + Ab = a(A-b) - A(A-b) = (A-b)(a-A) > 0 It follows that Ab' > ab, so the product of the numbers in the new set is greater than the original product. That means that the new geometric mean has increased. We now repeat the process, replacing the largest number in the new set by A and the smallest number by the new b' = a+b-A. In this way the numbers will eventually all equal A, and the geometric and arithmetic means become equal. But at each stage the geometric mean has been increased while the arithmetic mean has remained constant. It follows that the original geometric mean was less than the arithmetic mean. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 08/21/99 at 02:41:22 From: Tania Jacob Subject: Re: Partitions Thanks for your help. Is there a formula or way to tell what the partition size to maximize the product would be for any number? I have proved that the maximum product occurs when all the elements are e but I have no idea why it is. Also it seems to work only for partitions of large numbers, but my proof includes all numbers. Help! Date: 08/21/99 at 09:22:51 From: Tania Jacob Subject: Re: Partitions So sorry to bother you yet again, but I don't quite understand the proof involving arithmetic and geometric means. We haven't studied them much in school. Are you saying that the number to be partitioned is A, the arithmetic mean? And that the geometric mean is the product? And a, b, c, ... are the elements? I also don't get the last bit where you say eventually all the numbers will equal A. I guess you don't mean A is the number to be partitioned then? TJ Date: 08/21/99 at 10:07:35 From: Doctor Anthony Subject: Re: Partitions No. A = arithmetic mean of the numbers. So if there are n numbers, the number to be partitioned is nA = N. The product of all the partitions is then A*A*A*... to n factors = A^n and this will be the maximum product of the partitions of N. (that is, the partitions are equal). - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 08/22/99 at 00:16:11 From: Tania Jacob Subject: Re: Partitions Okay, I get it now. I still need to know if there is a formula to find which partition gives the maximum product. I guess there isn't, because I tried numbers to 200 and couldn't find a pattern. Why is it true that the element size to maximize the product is e only for large numbers? The proof I found is as follows: y = x^(n/x) ln(y) = (n/x)ln(x) y' = x^(n/x)(-nln(x)/x^2+n/x^2) = 0 at maximum x^(n/x)n/x^2(1-lnx) = 0 x = e and n is any number so I would have thought that if it was only true for large numbers I would have to find lim n-> infinity or something like that. That proof says it should work for all numbers but I don't see how. Date: 08/22/99 at 06:50:13 From: Doctor Anthony Subject: Re: Partitions If the expression x^(n/x)(n/x^2) (1- ln(x)) = 0 then you require 1 - ln(x) = 0 ln(x) = 1 x = e and this is independent of n. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 08/23/99 at 03:40:59 From: Tania Jacob Subject: Re: Partitions And since it's independent of n, it should be true for all numbers? Date: 08/23/99 at 07:00:07 From: Doctor Anthony Subject: Re: Partitions Yes. That is correct - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 08/24/99 at 04:36:29 From: Tania Jacob Subject: Re: Partitions How can it be correct for all numbers? Take 13; the maximum is (13/5)^5, for which the element size is 2.6, not e. Date: 08/24/99 at 11:29:25 From: Doctor Anthony Subject: Re: Partitions I'm not sure what you are doing here. If element size is e, then y = e^(13/e) = 119.39 while (13/5)^5 = 118.8 - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 08/25/99 at 02:41:11 From: Tania Jacob Subject: Re: Partitions Okay so what does the partition look like? The one for 5 is [2.6, 2.6, 2.6, 2.6, 2.6]... so with the element size e, there would be 4.782... numbers in the partition? How does that work? Date: 08/25/99 at 07:47:51 From: Tania Jacob Subject: Re: Partitions Sorry to bother you again, this is the last question, I promise. Is there any way to look at the problem so that the answer e makes more sense? Like any way to relate it to how the graph of e is its own derivative or something like that? Or should I just accept it as one of the mysteries of life? TJ Date: 08/25/99 at 07:54:30 From: Doctor Anthony Subject: Re: Partitions If you require an integer number of partitions, take the nearest integer to 4.782, namely 5. However, your question was what was the optimum partition size. Incidentally, the theory of partitions is normally concerned with integer partitions, so that 2.6 would not be considered a valid number for the partition. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/