highest product of the numbers that sum to $100$

Question

what is the highest product of the numbers that sum to 100

for example $100 = 1+1+1+1+1+1+1+\ldots+1$ the product of these is just $1^{100} = 1$

$100 = 99 + 1$ the product of these is $99\times 1$

the numbers have to be positive integers

do the numbers all have to be the same - for example I think it is $2^{50}$

Answer 1

The arithmetic-geometric-mean equation says that $\sum_{i=1}^{n}{\frac{a_i}{n}}\geq\sqrt[n]{\prod_{i=1}^n{a_i}}$.

If you enter your condition on the left side and look at different values for $n$, you might find a solution.

Edit: This method works well to guess a solution, which is that most of your numbers will be $3$, and by trying that we can find $3^{32}\cdot 2^2$. Now we can go about proving that this indeed the maximum:

Assume that any $a_k$ of your numbers is greater than $4$. We could then substitute this number by $\frac{a_k}{2}+\frac{a_k}{2}$, which have a product larger than $a_k$, since $\frac{a_k}{2}^2\geq a_k \Leftrightarrow a_k\geq 4$.

(If $a_k$ is odd, we can do the same thing with two numbers with difference $1$.)

From this we can conclude that there can be no numbers greater than $3$ in your sum. Also, there can be no $1$s, because $x+1\ge x\cdot 1$, so you would get a large product by merging the $1$ with another number $x$.

Hence, we have a selection of $a$ $3$s, and $b$ $2$s, where $3a+2b\leq 100$. Formally, we have to look at the cases $3a+2b=100, 3a+2b=99$, since if the sum was smaller than $98$ we could simply add a $2$.

Thus, we can write our product as $3^a2^{\frac{100-3a}{2}}$. If we look at this function and its maximum/monotony properties the only possible values for a maximum are $a=32, a=33$. Comparison leads to the maximum being at $a=32, b=2$.

Another possibility with less calculus would be to look at $3\cdot 3\geq 2\cdot 2\cdot 2$, immediately telling us that there cannot be three or more $2$s, else we could, again, substitute them with two $3$s. In hindsight, this way might actually be a lot quicker and requires no differentiation...

In any case, with both variants we are done, and you have your maximum being what quite some people have pointed out so far.

Answer 2

If we write a continuous version $f(x)=x^{\frac{100}{x}}$ it maximum is when $x=e$, the closest natural number is 3 so the maximum is $3^{32}*4$.

I will add that $f(x)=x^{\frac{b}{x}};\ \forall b\geq 1$ have a maximum on $x=e$.

We need to see now that any composition will be lesser number that just an unique exponential. I write $$f(x's)=x_0^{\frac{b-\sum_{i}c_i}{x_0}}\cdot x_1^{\frac{c_1}{x_1}}\cdot x_2^{\frac{c_2}{x_2}}\cdots x_n^{\frac{c_n}{x_n}};\ c_i\neq c_j,\ \sum c_i<b\\ x_i,b,c_i>1$$

From above we can see that the maximum for any multiplier is when it base is $x_i=e$ so you can see that for any $c_i$ we choose it maximum value will be related to a base $x_i=e$ so doesnt exist any composition with $x_i\neq e$ that make the function to have a greater maximum choosing any $c_i$ decomposition that you want.

This translated to natural numbers put the maximum with $x=3$, i.e. no closest natural number to $e$ that $3$ than lead to a number f(n) closest to f(e):

$$|f(e)-f(3)|<|f(e)-f(n)|\ \forall n\in \Bbb N-\{3\}$$

And we can add that if $0\not\equiv b \mod 3$ then the next number close to $f(e)$ is $f(2)$ so we must compose the number with powers of base 3 and 2. I.e.: $$r\equiv b\mod 3\ \rightarrow f(b)=3^{\frac{b-c}{3}}2^{\frac{c}{2}}\begin{cases}r\equiv 0, f(b)=3^{\frac{b}{3}}\\r\equiv 1, f(b)=3^{\frac{b-4}{3}}*4\\r\equiv 2, f(b)=3^{\frac{b-2}{3}}*2\end{cases}$$

Answer 3

Let's look at a factorisation containing the term $n$. We have $2(n-2)=2n-4$ so if $n\ge 4$ we have $2(n-2)= 2n-4 \ge n$, and replace $n$ with $2, n-2$, which does not reduce the product and may increase it.

If $1$ appears in the sum we can add it to another summand, which clearly increases the product without changing the sum.

So we get a sum consisting of terms which are either $2$ or $3$. Then we note Barak's observation that $3\cdot 3 \gt 2\cdot 2 \cdot 2$

Answer 4

Let's say a set $S=\{x_i\}:i\in \{1\to n\}$ for some $n\in\mathbb{N}$ is the optimal set. Since $\forall x \geqslant 4 : x * 2 \geqslant x + 2$, the set doesn't have any element $x \geqslant 4$ because we can take it out of the set and add a two and a $(x-2)$ instead. now for elements strictly smaller than 4: adding a $1$ want help since $x*1 = x$. However, comparing 2 to 3, we can find that $3*2 = 2*3$ which means adding 3 two times is equal to add 2 three times but $3*3>2*2*2$ which means we should switch as many sets of (2*2*2) to (3*3) as possible. Here we have three different cases which are the values for sum modulo 3. The case of 100 is 1 but let's speak generally.

for 0 the number can be divided by 3 and we are done.

for 2 we can add a 2 at the end with affecting threes so the answer is a 2 and $x/3$ threes.

The case of one is a bit tricky that when divided by 3 we have a rest of one so we even ignore it since $x*1 = x$ or we can take a three out if $x > 3 (x\neq1)$ and add two twos so we're comparing 2*2 to 1*3 and 2*2 is bigger so in this case we have 2 twos and a rest of threes.

In conclusion the answer to your question should be 2 twos and $(96\div3=32)$ threes

Answer 5

This can be solved in $O(n^2)$ by a divide-and-conquer approach: finding the best "split point" and using the product of the max subproducts, or no split at all.

$$f(n) = \max(n, f(n-1)f(1), f(n-2)f(2), \dots, f(1)f(n-1))$$

It should work if $\max$ or multiplication are replaced with associative operations.

Here is a python example:

from functools import cache

@cache
def f(n):
    return max((n, *(f(i)*f(n-i) for i in range(1,n))))

print(f(100))

$f(100) = 7412080755407364 = 3^{32} \times 2^2$