Maximum of $a_1 \cdot a_2 \cdots a_n$ given $a_1 + \cdots + a_n = 1000$?

Question

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:

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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