Partitions and Products

Date: 01/02/2003 at 15:07:08
From: Clive
Subject: Partitions and products

An integer, n, is divided into parts, e.g. 10 = 3+3+2+2 or 
10 = 2.5+2.5+2.5+2.5. What is the best way of dividing the number so 
that the product of the parts will be as large as possible? Is there 
a universal law that tells us what partition will produce the 
maximum product for any given number? And can such a law be proved?

Thanks for your time.

Date: 01/03/2003 at 12:34:57
From: Doctor Anthony
Subject: Re: Partitions and products

We start by obtaining the partition of 12 into a pair of numbers 
that produces the MAXIMUM PRODUCT.

If you let the numbers be x and 12-x then you require the value of x
that makes the product, y, such that  

          y = x(12-x)  a maximum.

          y = 12x - x^2

If you plot a graph of y against x you will get an upside-down 
parabola cutting the x-axis at x=0 and x=12. By symmetry we can see 
that its maximum point will occur at the value  x=6. That is when the 
two partitions are equal. So the maximum product is 6 x 6 = 36.

If you choose other numbers you will always find that the product is a 
maximum when the two parts are equal.

Consider also the number 12 being split into triples, quadruples, etc.

Splitting into 6 parts each of size 2 gives  2^6 = 64

and splitting into 4 parts each of size 3 gives  3^4 = 81

The theoretical maximum occurs when you split the given number into
parts each of size e (= 2.71828). To prove this we need to use the 
calculus, but if we try parts of size e we get 12/e = 4.41455; such 
parts and the product would be

    e^(4.41455) = 82.6449   and this is the theoretical maximum. 

As a general rule if each part is close to e = 2.718, then you will be 
close to the maximum product. Of course we must have an  integral 
number of parts.

The method is as follows. First divide the number by e.

So if the number is 20 we get 20/e = 7.3576

We want a whole number of parts, so take the nearest integer to 7.357,
namely 7.

Therefore we will have 7 parts and each part will be 20/7 = 2.857
and the required product is 2.857^7 = 1554.26

Check. If we took 8 parts each of size 20/8 = 2.5 then the product
would be 2.5^8 = 1525.88

As you can see this is slightly less. And if we take 6 parts of size
20/6 = 3.333, the product is 3.3333^6 = 1371.74, again less than our
best value 1554.26

Proof that Partitions of Size e will Maximize the Product
---------------------------------------------------------

Suppose the number is N.  We divide N into n parts each of size N/n; 
then the required product is 

        P = (N/n)^n    and we must find n to maximize P.

Taking logs   ln(P) = n.ln(N/n)

              ln(P) = n[ln(N) - ln(n)]  and differentiating

          1/P dP/dn = [ln(N) - ln(n)] + n[0 - 1/n]

              dP/dn = P[ln(N) - ln(n) - 1]  = 0  for max or min

putting the bracket equal to 0 we get

                      ln(N/n) = 1

                          N/n = e

so the optimum product occurs when the size of each partition is e. 

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/08/2003 at 14:17:33
From: Clive
Subject: Thank you (Partitions and products)

Thanks for all your help Dr. Anthony. It helped a lot!