Determine the greatest number, who is the product of some positive integers, and the sum of these numbers is $1976.$
Problem
Source: IMO ShortList, USA 1, IMO 1976, Day 2, Problem 4
Tags: number theory, Product, maximization, IMO, imo 1976
13.11.2005 01:38
Did I understand this question well: You have to find largest number which can be represented as $xy$ s.t. $x+y=1976$? Because if that is a question then it is trivial: $x+y\geq 2\sqrt{xy}$ so $(x+y)^2\geq 4xy$ so that number is $\frac{1976^2}4=976144$ m@re
13.11.2005 03:31
You can get a number which is MUCH bigger. For example, you could get $2^{988}$
13.11.2005 03:49
The biggest number you can find is $2.3^{658}$. Proof: Assume there was any factor 5 or more. we can split 5=2+3 which restults in a factor 6>5. Same for numbers larger than 5. So there are none. Thus we have the optimal number is of the form $2^m.3^n$. And since $3^2>2^3$, we need as much as possible into 3's, thus we end up with $2.3^{658}$.
13.11.2005 21:01
Well, that's why I asked did I understand this question
13.11.2005 21:58
Maybe we can find more: If $x_1,x_2,...,x_n$ are reals with $\sum x_i = 1976$, what is the maximum value $\prod x_i$ can obtain? Or maybe easier to start with, what is the value of $n$?
13.11.2005 22:52
Simple computations gives that when $n$ is given, it's optimal to take $x_1=x_2=...=x_n$. So we want $(\frac{a}{n})^n$ ($a=1976$ here) to be as big as possible. Deriving $f(x)=(\frac{a}{x})^x=e^{x \ln \frac{a}{x}}$ gives $f'(x)=e^{x \ln \frac{a}{x}} (ln(\frac{a}{x})-1)$, so it attains it's only maximum at $x=\frac{a}{e}$. Now $n$ has to be the next greater or smaller integer (it's monotonous on both sides).
29.09.2009 15:48
I just base cashed using AM-GM; $ \left(\frac{1976}{n}\right)^n \ge a_1 a_2 ... a_n$ Then, as the product was an integer n must be a factor of 1976 and the prime factors of 1976 are; 2,2,2,13,19 then consider all combinations of these. However, I don't know if I am missing something - it just seems a bit too simple
08.07.2013 15:17
Exactly the same except that i explained a bit more on why we chose (2 and 3 and 3)not (4 and 4) or (5 and 3) or(1 and 4 and 3)
08.07.2013 16:04
how do you know you must do an additional 2? how do you know that we should not separate the 2's and distribute them onto 3's?
08.07.2013 16:20
what we know that is that $3^4>4^3$, but this does not mean $3\times3\times2>4\times4$ (without calculation)
08.02.2018 14:59
So what is the answer here?
25.10.2019 18:36
Peter wrote: Proof: Assume there was any factor 5 or more. we can split 5=2+3 which restults in a factor 6>5. Same for numbers larger than 5. So there are none. For this we first need to prove this claim. Anyone here please prove this.
15.10.2021 19:09
The critical part is it says about positive integers. If positive reals, then the answer is $e^{\frac{1976}{e}}$. As it says for positive integers then have to work a little. We get from AM-GM that $\left(\frac{1976}{n}\right)^n\geq t$ where $t$ is the product of $n$ integers. To maximize the value of $f(x)=\left(\frac{1976}{x}\right)^x$ we have to find the first derivative of this then have to make it zero. Applying chain rule we have $f'(x)=e^{xln\frac{1976}{x}}\cdot f'(xln\frac{1976}{x})=e^{xln\frac{1976}{x}}\cdot (ln\frac{1976}{x}-1)$. Hence we get $ln\frac{1976}{x}-1=0\Longrightarrow x=\frac{1976}{e}$ We have to do some case work. We have find the integer solutions of the plot of $f(x)$ and the highest $y$ value is finally the answer. The value $e^{\frac{1976}{e}}$ is useful for the reason that the nearest values of it will be actually the answer (I think). The rest is little boring therefore I didn't find.
15.10.2021 19:40
If @above's solution is correct, then we have a nice way of giving explicit computations for $\lfloor e^{\frac{n}{e}}\rfloor$ for all positive integers.
15.10.2021 20:12
starchan wrote: If @above's solution is correct, then we have a nice way of giving explicit computations for $\lfloor e^{\frac{n}{e}}\rfloor$ for all positive integers. I have found error in my solution. Whatever. you can show the way of computing the value of $\lfloor e^{\frac{n}{e}}\rfloor$ what you have found.
17.10.2021 07:57
Abdullahil_Kafi wrote: The critical part is it says about positive integers. If positive reals, then the answer is $e^{\frac{1976}{e}}$. As it says for positive integers then have to work a little. We get from AM-GM that $\left(\frac{1976}{n}\right)^n\geq t$ where $t$ is the product of $n$ integers. To maximize the value of $f(x)=\left(\frac{1976}{x}\right)^x$ we have to find the first derivative of this then have to make it zero. Applying chain rule we have $f'(x)=e^{xln\frac{1976}{x}}\cdot f'(xln\frac{1976}{x})=e^{xln\frac{1976}{x}}\cdot (ln\frac{1976}{x}-1)$. Hence we get $ln\frac{1976}{x}-1=0\Longrightarrow x=\frac{1976}{e}$ We have to do some case work. We have find the integer solutions of the plot of $f(x)$ and the highest $y$ value is finally the answer. The value $e^{\frac{1976}{e}}$ is useful for the reason that the nearest values of it will be actually the answer (I think). The rest is little boring therefore I didn't find. Umm you cannot have a nonintegral number of reals. $x$ must remain integer no matter what. You cannot have $x = \frac{1976}{e}$ because you cannot have those many positive reals. (this number should be an integer no matter what)
26.02.2022 07:01
Suppose some positive integer $k\ge 5$ is there. Then replace $k$ with $2$ and $k-2$. We have $2(k-2)=2k-4>k$, so it is more optimal. If some $k=4$ is there, then replace it with two $2$'s. Thus, optimally, all these positive integers are either $2$ or $3$. Now we can replace three twos with two threes, because $3^2>2^3$. So the greatest is $\boxed{2\cdot 3^{658}}$.
16.03.2022 19:36
Let $x_1, x_2, \dots, x_n$ be positives summing to $1976$ and $M$ be the max product of $x_1x_2 \dots x_n$. By observation we find that $M$ is of the form $2^r3^s$ implying that $2r+3s=1976$. It's obvious that to get max we must have as many 3's more than 2's possible (since $3^2> 2^3$). So, $2r \equiv 1976 ( \text{mod } 3) \implies (k,l)= (1,658) \implies M=2 \cdot 3^{658}.$ $\square$