Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!decvax!ittatc!dcdwest!sdcsvax!sdcc6!sdcc3!kemasa
From: kemasa@sdcc3.UUCP (kemasa)
Newsgroups: net.puzzle
Subject: Re: Find a set of ...
Message-ID: <3201@sdcc3.UUCP>
Date: Fri, 14-Mar-86 15:27:29 EST
Article-I.D.: sdcc3.3201
Posted: Fri Mar 14 15:27:29 1986
Date-Received: Sun, 16-Mar-86 04:11:19 EST
Distribution: na
Organization: U.C. San Diego, Academic Computer Center
Lines: 170


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.