kemasa@sdcc3.UUCP (kemasa) (03/14/86)
The question of a set of number whose sum = C with the maximum product.
n ___
__ \
max || Xi over all partitions (n): > Xi = C
i=1 /___
1) Start by considering a fixed value of n.
Maximize:
n
___
\
> Ln[Xi] Since Ln is monotonic increasing for increasing X
/___
i=1
Given:
n
___
\
> Xi = C
/___
i=1
1 \
Lagrange multiplers => --- = /\ forevery i
Xi
n
___
. \ 1 \ n
. . > --- = C => /\ = ---
/___ \ C
i=1 /\
+-------------------------+
| C |
| Xi = --- for every i |
| n |
+-------------------------+
2) For each n, max is:
n
___
\ C C
> Ln[---] = nLn[---]
/___ n n
i=1
C C -1
To maximize xLn[---] : Ln[---] + x(---) = 0 {Zero}
x x x
C C C
=> Ln[---] = 1 --- = e x = ---
x x e
Then since x (or n) must be an integer, test integer values above and below x
C
3) C = 100, --- = about 36.7
e
=> n = 37
The Graphs are just to show that this is really true.
Graph of [x Ln[100/x]] for x = 1 to 100
| *************
| **** ******
| *** ****
30 *** ****
| ** ***
| * ***
| ** **
| * ***
20 * **
| * **
| * **
| ** **
10* *
|* **
|* **
| **
| **
0-------------20--------------40-------------60-------------80--------------
Graph of [x Ln[100/x]] for x = 36 to 37
| ********************
| ******* *******
| *****
| *****
36.786 ***
| ***
| ***
| ***
36.784 **
| ***
| **
| **
36.782 **
| **
| **
| **
36.78
36-----------------------------------36.5----------------------------------37
Graph of Ln[100/x]-1 for x = 1 to 100
|
|*
3*
|*
|**
| *
2 *
| **
| **
| **
1 ***
| *****
| *****
0-------------20--------------40-------------60-------------80--------------
| *********
| ************
| ****************
-1 **********
Graph of Ln[100/x]-1 for x = 1 to 100
|**
0.02***
| ****
| *****
| ****
| *****
| ****
0.01 *****
| *****
| ****
| *****
| ****
| ****
06-----------------------------------36.5----------------------------------37
| *****
| ***
| *****
| ***
This work re-printed with permission, I am not that into math do
to such a thing.
Kemasa.baron@harvard.UUCP (Jeff Baron) (03/17/86)
In article <3201@sdcc3.UUCP> kemasa@sdcc3.UUCP (kemasa) writes: > >The question of a set of number whose sum = C with the maximum product. > Try to do this when the set of numbers equal to C can be composed only of integers, ie. find the set of integers whose sum is equal to C and whose product is as large as possible. -- Jeff Baron {allegra,genrad,ucbvax}!harvard!baron