8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $3\cdot3$ by itself is "better" than $2\cdot2\cdot2$ because it yields $9$ instead of $8$, while both options "consume" $6$ out of the sum. So there's got to be something better than $2^{50}$. $\endgroup$ – barak manos Oct 9 '14 at 18:20
  • $\begingroup$ $3^{33}\times 1>2^{50}$ $\endgroup$ – Alessandro Codenotti Oct 9 '14 at 18:21
  • 1
    $\begingroup$ Best one I found is $3^{32}\cdot4$. $\endgroup$ – barak manos Oct 9 '14 at 18:24
  • $\begingroup$ is there a method for this rather than just trial and error $\endgroup$ – zebra1729 Oct 9 '14 at 18:30
  • $\begingroup$ @Hamou: to get multidigit exponents, put them in braces, so 2^{50} gives $2^{50}$ instead of $2^50$ This works lots of places in $\LaTeX$ $\endgroup$ – Ross Millikan Oct 9 '14 at 19:17
5
$\begingroup$

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, for obvious reasons.

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 6$, immediately telling us that there can be no more than $3$ $2$s, else we could, again, substitute them with $2$ $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.

$\endgroup$
  • $\begingroup$ +1 Very interesting proof. It's always a little surprising to see discrete theorems with proofs involving differentiation. But you're right that the latter method of proof would be more elegant. $\endgroup$ – Tyler Oct 10 '14 at 5:06
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry for going into a bit more detail here, since your argument is definitely valid and leads to the correct solution. But I do not see how the conclusion "the closest natural number is 3, so the maximum is" would possibly hold, being examined more closely? The assumption is correct, and you can prove it fairly easily, but I fail to see how this is a formal proof. $\endgroup$ – Some Math Student Oct 9 '14 at 18:39
  • $\begingroup$ Im not familiarized with the requirements of proofs but I think its work as a formal proof but we need to add the proof that the product of different and complementary product is a lesser number of an exponential, i.e., $(x-a)a < x^2$ and extend this notion for any division of x. $\endgroup$ – Masacroso Oct 9 '14 at 18:45
  • $\begingroup$ doesn't your function assume that all the numbers have to be the same - why can't they all be different or some be different $\endgroup$ – zebra1729 Oct 9 '14 at 18:55
  • $\begingroup$ I do not quite see where to go from there, but that might just be me. Have added my variation of a formal proof from there - I think the problem with your first comment lies that, while we do get an upper bound for the problem, we do not know what the function does on any values other than the maximum. We might not have all the same numbers in the result. @zebra, we get an upper bound for our product, not an exact solution. The upper bound you get by assuming all numbers are equal but not necessarily in $\mathbb{N}$, since that's where in AM-GM equality holds. $\endgroup$ – Some Math Student Oct 9 '14 at 18:57
  • $\begingroup$ @SomeMathStudent I still do not understand why making all the numbers equal gives the upper bound and how this relates to the AM GM inequality - isn't this to do with the nth root of the product $\endgroup$ – zebra1729 Oct 9 '14 at 19:00
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

    $\endgroup$

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Not the answer you're looking for? Browse other questions tagged or ask your own question.