Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Maximizing the Product of Partition Elements


Date: 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/   
    
Associated Topics:
High School Permutations and Combinations
High School Sets

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/