Results 1 to 7 of 7

Math Help - maximize integers product

  1. #1
    Junior Member
    Joined
    Jan 2007
    Posts
    26

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by anime_mania View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2008
    Posts
    6
    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...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by sean92t0 View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2008
    Posts
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by sean92t0 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: August 3rd 2010, 01:31 PM
  2. Replies: 5
    Last Post: March 24th 2010, 01:11 PM
  3. Matrix of integers whose inverse is full of integers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 02:02 PM
  4. Largest Product of Integers
    Posted in the Advanced Math Topics Forum
    Replies: 8
    Last Post: July 16th 2008, 07:31 AM
  5. Replies: 4
    Last Post: February 24th 2008, 03:08 PM

Search Tags


/mathhelpforum @mathhelpforum