Greatest product from a sum

Printable View

July 23rd 2007, 11:33 PM
DivideBy0

Greatest product from a sum

The sum of n positive integers is 19. What is the maximum possible product of these n numbers?

Can you also please explain why this is so?
July 24th 2007, 11:30 PM
CaptainBlack

Quote:

Originally Posted by DivideBy0

The sum of n positive integers is 19. What is the maximum possible product of these n numbers?

Can you also please explain why this is so?

Well as nobody else has answered this I will tell you what I know though its not a complete solution.

The arithmetic-geomentric mean inequality tells us that if there are $N$ numbers involved, and that these are $n_i,\ i=1, .. N$ , then:

$ \left[ \frac{19}{N} \right]^N \ge \prod_1^N n_i $

Regarding the lefthand side of this inequality as a function of N this has a maximum $\approx 1085.4$ when $N=7$ . So we have that the maximum posible value of the product of an integer partition of $19$ is less than or equal $1085$ .

The partition $3,3,3,3,3,2,2$ has product $972$ and I would not be supprised if this were the maximum, but have not done enough to convince even myself that this is the case.

RonL
July 25th 2007, 02:06 AM
CaptainBlack

Quote:

Originally Posted by CaptainBlack

Well as nobody else has answered this I will tell you what I know though its not a complete solution.

The arithmetic-geomentric mean inequality tells us that if there are $N$ numbers involved, and that these are $n_i,\ i=1, .. N$ , then:

$ \left[ \frac{19}{N} \right]^N \ge \prod_1^N n_i $

Regarding the lefthand side of this inequality as a function of N this has a maximum $\approx 1085.4$ when $N=7$ . So we have that the maximum posible value of the product of an integer partition of $19$ is less than or equal $1085$ .

The partition $3,3,3,3,3,2,2$ has product $972$ and I would not be supprised if this were the maximum, but have not done enough to convince even myself that this is the case.

RonL

Now as

$ \left[ \frac{19}{9} \right]^9 \approx 832.9 $

and

$ \left[ \frac{19}{5} \right]^5 \approx 792.4 $

The above example of a 7-partition with a product of $972$ shows that the partition that gives the maximum product must be a 6, 7 or 8-partition.

(Exhaustive search shows that $972$ is indeed the maximum product and it can be achived with either a 6 or a 7-partition.

RonL
July 25th 2007, 03:25 AM
CaptainBlack

Quote:

Originally Posted by CaptainBlack

The partition $3,3,3,3,3,2,2$ has product $972$ and I would not be supprised if this were the maximum, but have not done enough to convince even myself that this is the case.

The reason for guessing that this partition is a good candidate for the maximum product is that the arithmetic-geometric mean inequality is an equality when all the numbers are equal. We cant achive that in this case as 19 is prime, but we can look at partitions where the elements are as near equal as possible, and that is what I did here.

The 6-partition of 19 which achives the maximum product can also be found im this way.

RonL
July 27th 2007, 10:38 AM
ray_sitf

What about [19/(19/e)] to the power of (19/e)?

This gives 1085.405992...

I know the OP wanted integers, but this suggests the following procedure.

If the number leaves a remainder of 2 when divided by three, then the max. answer is 3*3*3*...*2.
If the number leaves a remainder of 1 when divided by three, then the max. answer is 3*3*3*...*2*2.
If there is no remainder on division by three, then it's 3*3*3*...*3.

E.g. for 23 it's 3^7 * 2, and for 25 it's 3^7 * 2 * 2
July 27th 2007, 10:52 AM
CaptainBlack

Quote:

Originally Posted by ray_sitf

What about [19/(19/e)] to the power of (19/e)?

This gives 1085.405992...

I know the OP wanted integers, but this suggests the following procedure.

I know what you are talking about, but I doubt many others will

RonL
July 27th 2007, 11:09 AM
CaptainBlack

Quote:

Originally Posted by ray_sitf

I know the OP wanted integers, but this suggests the following procedure.

If the number leaves a remainder of 2 when divided by three, then the max. answer is 3*3*3*...*2.
If the number leaves a remainder of 1 when divided by three, then the max. answer is 3*3*3*...*2*2.
If there is no remainder on division by three, then it's 3*3*3*...*3.

E.g. for 23 it's 3^7 * 2, and for 25 it's 3^7 * 2 * 2

Very likely, but you will need to prove it.

RonL
July 27th 2007, 11:59 PM
DivideBy0

You're correct Captainblack, the answer is 972.
I had a hard time understanding the inequality, but I guess as long as I take it for granted I should be fine.

Also, is it an actual fact that 3 is the best integer and $e$ is the best number to use for something like this?
July 28th 2007, 06:14 AM
CaptainBlack

Quote:

Originally Posted by DivideBy0

You're correct Captainblack, the answer is 972.
I had a hard time understanding the inequality, but I guess as long as I take it for granted I should be fine.

Also, is it an actual fact that 3 is the best integer and $e$ is the best number to use for something like this?

The logic says that the nearest integer to N/e is a good choice for the
number of terms in the sum and product, and that lots of 3's and a few 2's
will get you close to the maximum for the product, but its not definitive.
For instance you can get as large a product with 6 terms and with 7 when
the sum is 19.

RonL