6
$\begingroup$

I am not sure what I am doing wrong in my solution to this problem:

Find positive numbers $n$ and $a_1, a_2, \dots, a_n$ such that $a_1+a_2+\dots +a_n\le 1000$ and the product $a_1a_2\dots a_n$ is as large as possible.

I have that $AM-GM$ gives us $\dfrac{a_1 + \cdots + a_n}{n} = \dfrac {1000}{n} \ge \sqrt[n]{a_1 \cdots a_n}$. Regardless of $n$, we get equality (and therefore maximum of the product) $\iff$ $a_1 = a_2 = \cdots = a_n$, so the inequality above becomes $\dfrac {1000}{n} = \sqrt[n]{a_1^n}$, or $\dfrac {1000}{n} = a_1$. To maximize $a_1$, we can take $n = 1$. But this is obviously a wrong answer.

EDIT: This is the solution they give:

enter image description here

$\endgroup$
8
  • $\begingroup$ Oh, we are assuming $a_k$ must be natural? :-/ $\endgroup$ Mar 4, 2017 at 17:10
  • 1
    $\begingroup$ @SimplyBeautifulArt Well that's ok, I can work on the solution when they're naturals on my own. I just wanted to know what was wrong with my approach. But yeah they should've mentioned that they were naturals. $\endgroup$
    – Ovi
    Mar 4, 2017 at 17:11
  • $\begingroup$ What do you mean by AM-GM? $\endgroup$
    – Shaun
    Mar 4, 2017 at 17:27
  • $\begingroup$ It is a funny thing. By maximising $a_1$, you essentially minimized $(a_1)^n$, with the exception of $a_1=1$. $\endgroup$ Mar 4, 2017 at 17:28
  • $\begingroup$ @Shaun en.wikipedia.org/wiki/… $\endgroup$ Mar 4, 2017 at 17:28

5 Answers 5

4
$\begingroup$

What you have shown is this:

For a fixed $n$, and $a_i\in \mathbb R_{>0}$, then the maximum product is attained when $a_i=\dfrac{1000}{n}$ for all $i$.

But then the product is $\left(\dfrac{1000}{n}\right)^n$, not $\dfrac{1000}{n}$. And this product is not maximised when $n=1$; it is maximised when $n$ is about $\dfrac{1000}{e}$. (Specifically: take the two integers either side of $\dfrac{1000}{e}$, and see which of them gives a greater product.)

$\endgroup$
0
3
$\begingroup$

So, as your book suggests, we can establish that $a_i \le 4$: if we were to have $a_i > 4$, then $(a_i - 2 )(2) = a_i + (a_i - 4) > a_i$. Similarly $(a_i - 1)(1) < a_i$, so we have $a_i > 1$. Thus our $a_i$'s will all be $2$ or $3$ - which are approximately $e$, in connection with Simply Beautiful Art's answer - but $2 \cdot 2 \cdot 2 < 3 \cdot 3$ guarantees that there can be at most two $2$'s.

This is a fairly classic problem, and Art's answer can be a good starting point as to making an educated guess about the solution for the naturals.

$\endgroup$
1
  • $\begingroup$ It might be worthwhile to add that from the condition that there are at most two $2$s together with the fact that $1000\equiv 1\pmod 3$ we can conclude that there are exactly two $2$s. $\endgroup$
    – celtschk
    Mar 4, 2017 at 17:23
2
$\begingroup$

Note that when $a_1=a_2=\dots=a_n$, then $\frac{1000}n=a_1$. But then you try to find

$$\max[a_n]$$

which is not what we are looking for. What you want is

$$\max[(a_n)^n]=\max\left[\left(\frac{1000}n\right)^n\right]$$

You may however note that since the maximum occurs when $a_1=a_2=\dots=a_n$, then by directly using the original equations:

$$na_1=1000$$

$$a_1=\frac{1000}n$$

$$a_1\times a_2\times\dots\times a_n=(a_1)^n=\left(\frac{1000}n\right)^n$$

Which is much larger than what you initially presumed. By taking the derivative and finding the global maximum for $n\in\mathbb N$, we find the global maximum occurs at $n\approx1000/e=367.8$, and by comparing values around it, $n=368$ is our solution, with

$$a_1=2.718281828\approx e$$

and

$$(a_1)^n=5.8614\times10^{159}$$

for $a_n\in\mathbb N$, this is merely a question of whether $a_1=2$ or some bombination of $2$ and $3$, and this is easy to check that it should be as many $3$'s as possible.

$\endgroup$
6
  • $\begingroup$ Note that $3^{332}\cdot 2^2\approx 1.015\cdot 10^{159}$. $\endgroup$
    – celtschk
    Mar 4, 2017 at 17:18
  • $\begingroup$ How does that relate to anything here? $\endgroup$ Mar 4, 2017 at 17:20
  • $\begingroup$ That's the maximum number given in the quoted solution. $\endgroup$
    – celtschk
    Mar 4, 2017 at 17:34
  • $\begingroup$ Yeah, my bad. Posted this answer before solution was given, where the problem was supposedly tasked with $a_n\in\mathbb N$. $\endgroup$ Mar 4, 2017 at 17:38
  • $\begingroup$ I'm a little confused by your first sentence. We know that $AM=GM \iff a_1 = a_2 = \cdots = a_n$. So $a_1 = a_2 = \cdots = a_n \implies AM = GM \implies \dfrac {1000}{n} = \sqrt[n]{a_1 \cdot a_2 \cdots a_n} \implies \dfrac {1000}{n} = \sqrt[n]{a_1^n} \implies \dfrac {1000}{n} = a_1$ $\endgroup$
    – Ovi
    Mar 4, 2017 at 19:46
2
$\begingroup$

How to do this without calculus:

Your error is that although by taking $n = 1$ you maximize the $a_1$ term that minimizes the exponent. $a = 1000 > b = 500 = 1000/2 > .... k = 1000/n$ but $1000^1 < 500^2 < ..... k^n$.

So while you are correct $a_k = 1000/n$ (or closest integer to it). You haven't any idea what $n$ should be.

Consider a product $a_1a_2....a_n; a_1 + a_2+a_3+.... + a_n = M$.

Our goal is to maximize the product.

1: Unless $M = 1$ (in which case the only product is $1 = a_1 = 1$) none of the $a_k$ will equal $1$.

If you have a term equaling $1$ and another term equaling $a_k$ you can replace these two terms with the single term $b = a_k+1$. This will increase the product (as $a_k + 1 > a_k*1$) while maintaining the sum (as $b = a_k + 1$).

2: There will be no terms larger than 4.

If we have a term $a_k > 4$ we can replace this single term with two terms $b = \lfloor a_k/2 \rfloor$ and $ = \lceil a_k/2 \rceil$. If $a_k$ is even $a = b= a_k/2$. If $a_k$ is odd $a= \frac {a-1}2; b = \frac {a+1}2$.

The sum is maintained ($a + b = a_k$) but the product is increased: if $a_k$ is even then $bc = \frac {a_k}2\frac {a_k}2 = \frac {a_k^2}4 > \frac {a_k*4}4 = a_k$. If $a_k$ is odd then $a_k \ge 5$. Then $bc = \frac {a_k-1}2\frac {a_k+1}2 = \frac {a_k^2 - 1}4 = \frac {a_k^2}4 - 1/4 \ge \frac {a_k*5}4 -1/4 = a_k + \frac {a_k}4- 1/4 > a_k$.

2a: If any of the terms are $a_k =4$ we can replace $a_k$ with two terms, $b = c =2$ with no change to the sum or the product.

3: There will be at most one $4$ or one pair of $2$s.

If there are $a_k = 4$ and $a_j= 4$, we may replace them with $b=3;c=3; d=2$. The sum is preserved as $a_k + a_j = b+c+d$ but the product is increased because $a_k a_j = 16$ while $bcd = 18 > 16 = a_ka_j$.

If there are $a_k =2; a_j = 2; a_l =2$ we may replace them with $b=c= 3$. The sum is preserved as $a_k + a_j + a_l= a+b$, but the product is increased because $a_k a_j a_l= < 8 < 9 = bc$.

Putting all those facts together we realize the terms must be either a) all $3$s (in which case $M$ is a multiple of $3$). b) all $3$s and one $2$ (in which case $M \equiv 2 \mod 3$) or c) all $3$s and two $2$s or alternatively all $3$ and one $4$ (in which case $M \equiv 1 \mod 3$).

So if $M = 1000= 3*332 + 4$, the highest possible product is $n = 333$ or $n= 334$ with $a_1$ through $a_{332} = 3$ and either $a_{333}=4$ or $a_{333}=a_{334} = 2$.

==== old answer (same idea but I think if modified significantly to warrant my current answer as different) ====

How to do this without calculus:

Let $a_1a_2.....a_n$ be the largest product.

If $a_i = 4$ you could replace $a_i =4$ with $a_{i1} =2; a_{i2} = 2$ and$a_i = a_{i1}+a_{i2}; a_i = a_{i1}a_{i2}$ with no change in the product.

If $a_i > 4$ you could replace $a_i=4$ with $a_{i1} = (a_i - 2); a_{i2} = 2$ to get $a_{i1}a_{i2} = 2a_i - 4 = a_i + (a_i -4) > a_i$ while $a_i = a_{i1}+a_{i2}$. So this will make the product bigger.

So the maximum product need not contain anything larger than $3$.

If the product contains any $a_i = 1$ and some $a_j$, then replacing both of those with $a_k = a_j + 1$ will make the product bigger as $a_j + 1 > a_j*1$.

So the list of terms will contain only $3$s and $2$s.

The question becomes how many threes and how many $2$s.

Well. Any three $2$s, $2*2*2=8$, can be replaced with $3*3 = 9$ while $2+2+2 = 3+3$. So there will be at most two $2$s. The rest will be $3$s.

If $k=1000$ is divisible by $3$ they will all be $3$. (It isn't and they aren't.)

If $k = 1000$ has remainder two when divided by $3$ there will be one $2$. (Ditto.)

If $k = 1000$ has remainder one when divided by $3$ (it does) there will be two $2$s.

So the maximum product is $2^2* 3^{m}$ where $m = \frac {1000 - 2-2}3 = 332$.

$\endgroup$
4
  • $\begingroup$ There seem to be some typos in the case $a_i>4$. $\endgroup$
    – Martin R
    Mar 4, 2017 at 22:06
  • $\begingroup$ I don't see any typos, but then I seldom see my own typoes. $\endgroup$
    – fleablood
    Mar 5, 2017 at 3:45
  • $\begingroup$ The commas make it hard to read, huh? $\endgroup$
    – fleablood
    Mar 5, 2017 at 3:45
  • $\begingroup$ "If $a_i > 4$ you could replace $a_i =4$ ..." sounds confusing. And if you define $a_{i1} = (a_i - 1); a_{i2} = 2$ then $a_i = a_{i1}+a_{i2}$ does not hold. Perhaps you meant to define $a_{i1} = (a_i - 2); a_{i2} = 2$? $\endgroup$
    – Martin R
    Mar 5, 2017 at 8:16
1
$\begingroup$

Using the Lagrange's multipliers method, we have find the max of

$f(a_1,\ldots,a_n)=\prod_{i=1}^n a_i-\lambda\cdot (\sum_{i=1}^n a_i-1000)$

and hence we get a system of $n$ equations as follows:

$\frac{\partial f}{\partial a_i}=\prod_{\stackrel{j=1}{j\ne i}}^n a_j-\lambda=0$

for $i=1,\ldots,n$ plus the following extra equation for the constraint:

$\sum_{i=1}^n a_i-1000=0\qquad(*)$

In particular for $j$ and $j+1$ we have

$\frac{\partial f}{\partial a_j}=\prod_{\stackrel{i=1}{i\ne j}}^n a_i-\lambda=0$

and

$\frac{\partial f}{\partial a_{j+1}}=\prod_{\stackrel{i=1}{i\ne j+1}}^n a_i-\lambda=0$

Hence we find $a_j=a_{j+1}$ for all $j=1,\ldots, n$ and from the Equation $(*)$ it follows: $a_1=a_2=\ldots=a_n=\frac{1000}{n}$.

Hence the max is $\left(\frac{1000}{n}\right)^n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .