maximize integers product

**anime_mania** · April 13th 2008, 07:20 PM

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

**ThePerfectHacker** · April 13th 2008, 08:09 PM

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$ .

**ThePerfectHacker** · April 13th 2008, 09:12 PM

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.

**sean92t0** · July 16th 2008, 01:27 PM

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...

**ThePerfectHacker** · July 16th 2008, 01:32 PM

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 ?

**sean92t0** · July 16th 2008, 04:44 PM

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.

**ThePerfectHacker** · July 16th 2008, 06:05 PM

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$ .

Thread: maximize integers product

LinkBack

Thread Tools

Display

maximize integers product

Similar Math Help Forum Discussions

Circular numbers as opposed to integers and Gaussian integers?

Primitive Roots - product of integers <= n and rel prime to n

Matrix of integers whose inverse is full of integers

Largest Product of Integers

Choosing Non-Consecutive Integers from a list of N Integers

Search Tags