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!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.