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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search