1. ## maximize integers product

Hey guys, here is the problem
If a bunch of positive integers adds up to 20, what is the greatest possible product of these numbers?

I think its 1458 from 3*6*2=1458

Some please cheack to seeif it is right thanks

2. Originally Posted by anime_mania
Hey guys, here is the problem
If a bunch of positive integers adds up to 20, what is the greatest possible product of these numbers?

I think its 1458 from 3*6*2=1458

Some please cheack to seeif it is right thanks
I agree .

If you want a mathematical justification read on. We need a few facts to prove that no matter how hard we try that $3^6\cdot 2 = 1458$ is the best possible answer.

First, if $x,y\geq 0$ are integers (whole numbers) then $2x+3y\leq 2^x \cdot 3^y$. You might say the RHS is exponents and LHS is just addition so it makes sense that RHS is much larger than LHS so maybe in fact we should have $<$ instead of $\leq$. But that is not completely true. For small values $x=0,1 \ y=0,1$ we actually have equality.

Second, any integer $n\geq 2$ can be written in the form $n=2x+3y$ where $x,y\geq 0$ are integers. Do you see why this is true? See if you can figure this out.

Third, any representation that has $1$ amongs its summands (for example $9+9+1+1=20$) cannot be the maximum value. The reason is the follows. Say $a_1+a_2+...+a_k + 1 = 20$ is a representation then its product is $(a_1)(a_2)...(a_k)(1) = a_1a_2...a_k$. While $a_1+a_2+...+(a_k+1) = 20$ is also a representation and its product is $(a_1)(a_2)...(a_k+1)$. Which one is larger? The second one definitely because in the first product the first $k-1$ numbers are the same as in the second product while in the second product the last number, $a_k+1$, is larger than the last number, $a_k$, in the first product.

Now we are ready to state the main result.

Theorem: The maximum product for the representation $20$ is achieved where all the summands are $2$'s and $3$'s.

Proof: Say that $a_1+a_2+...+a_k = 20$ is a representation. To be maxed we require that each term $\geq 2$, look at the third fact we are using. Then each summand can be written as a sum of twos and threes (because each is $\geq 2$) by the second fact. Meaning $a_1 = 2x_1+3y_1$ and $a_2 = 2x_2+3y_2$ ... and $a_k = 2x_k + 3y_k$. Now $a_1a_2...a_k \leq 2^{x_1}3^{y_1}\cdot 2^{x_2}3^{y_2}\cdot ... \cdot 2^{x_k}3^{y_k}$ by the first fact we are using. But the point is we decomposed each $a_1,...,a_k$ into $2$'s and $3$'s. Meaning $20 = a_1 + ... +a_k = 2x_1+3y_1+...+2x_k+3y_k = \underbrace{(2+...+2)}_{x_1}+\underbrace{(3+...+3) }_{y_1}+...$, in fact the number of times $2$ appears is $x_1+...+x_k$ times and $3$ appears $y_1+...+y_k$ times. Which means this new representation is at least as big as the previous one. Thus, any representation which is maxed must be made out of $2$'s and $3$'s.

Finally we can solve the problem. Say that you have $x$ twos and $y$ threes then $2x+3y = 20$ and their product is $2^x3^y$. Thus, we want to maximize $2^x3^y$ subject to $2x+3y=20$. But this is simple. The only possibilities are: $(10,0),(7,2),(4,4),(1,6)$ and its respective sums are: $1024,1152,1296,1458$. Thus, the max product is $1458$.

3. We can in fact generalize this result. Say $N\geq 2$.

If $N\equiv 0(\bmod 3)$ the max product is $3^{N/3}$.
If $N\equiv 1(\bmod 3)$ the max product is $2^2\cdot 3^{(N-4)/3}$
If $N\equiv 2(\bmod 3)$ the max product is $2\cdot 3^{(N-2)/3}$.
(The idea is to get as many three's as possible).

You can prove these results by inducting on each of the three cases.

4. I just thought I would point out that the reason you want to maximize the number of 3s is because 3 is the closest integer to e. I dont think you mentioned that...

5. Originally Posted by sean92t0
I just thought I would point out that the reason you want to maximize the number of 3s is because 3 is the closest integer to e. I dont think you mentioned that...
What is the motivation behind why you say it has to be the closest to e ?

6. well in your previous post you said that the idea is to get as many 3s as possible and the well somewhat trivial reason why that 3 is close to e. Knowing that a product of e's would yield the highest product, had this been reals instead of integers.

7. Originally Posted by sean92t0
well in your previous post you said that the idea is to get as many 3s as possible and the well somewhat trivial reason why that 3 is close to e. Knowing that a product of e's would yield the highest product, had this been reals instead of integers.
1)Why would the product of $e$'s make the highest number possible?
2)It is not possible to have $e+e+...+e = N$ because $e$ is irrational.
3)I have an idea of what you might mean, look below.

Given a number $N\geq 2$. And let $x_1+x_2+...+x_k = N$ be positive real numbers. Then the maximum product which can be formed is when all are the same, so that product is $( \tfrac{N}{k})^k$. What is the value of $k$ which makes this the maximum value? We will solve this problem by first defining the function $f(x) = (\tfrac{N}{x})^x = \tfrac{N^x}{x^x}$ (where $x>0$). The maximum occurs when $f'(x) = 0$ (drawing a graph for various values of $N$ is very helpful). Solving this equation we get $x=\tfrac{N}{e}$. Let $[ ~ ]$ be the 'nearest integer function'. Then by the shape of the curve we have that the best integer value is $[ \tfrac{N}{e} ]$. For example, if we want to maximize the product of the sum for $N=10$ then $k = [\tfrac{10}{e}] = 4$. But then the maximized product is $(\tfrac{10}{4})^4 = 39.0625$.