Difference between revisions of "1976 IMO Problems/Problem 4"

m (Solution 3)
 
(4 intermediate revisions by 3 users not shown)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
{{solution}}
+
=== Solution 1 ===
 +
Since <math>3*3=2*2*2+1</math>, 3's are more efficient than 2's. We try to prove that 3's are more efficient than anything:
 +
 
 +
Let there be a positive integer <math>x</math>. If <math>3</math> is more efficient than <math>x</math>, then <math>x^3<3^x</math>. We try to prove that all integers greater than 3 are less efficient than 3:
 +
 
 +
When <math>x</math> increases by 1, then the RHS is multiplied by 3. The other side is multiplied by <math>\dfrac{(x+1)^3}{x^3}</math>, and we must prove that this is less than 3 for all <math>x</math> greater than 3.
 +
 
 +
<math>\dfrac{(x+1)^3}{x^3}<3\Rightarrow \dfrac{x+1}{x}<\sqrt[3]{3}\Rightarrow 1<(\sqrt[3]{3}-1)x</math>
 +
 
 +
<math>\dfrac{1}{\sqrt[3]{3}-1}<x</math>
 +
 
 +
Thus we need to prove that <math>\dfrac{1}{\sqrt[3]{3}-1}<4</math>. Simplifying, we get <math>5<4\sqrt[3]{3}\Rightarrow 125<64*3=192</math>, which is true. Working backwards, we see that all <math>x</math> greater than 3 are less efficient than 3, so we try to use the most 3's as possible:
 +
 
 +
<math>\dfrac{1976}{3}=658.6666</math>, so the greatest product is <math>\boxed{3^{658}\cdot 2}</math>.
 +
 
 +
===Solution 2===
 +
We demonstrate heuristically that 3's are the most efficient.
 +
As we know that the chosen numbers must be equal, by the AM-GM inequality, we wish to maximize <cmath> f(x) = \left(\frac{1976}{x}\right)^{x} </cmath>
 +
Simple logarithmic differentiation shows that <math>\frac{S}{x} = e</math> maximizes the given function. As <math>e</math> is approximately 2.71828, we use 2's and 3's only. 3's are optimal, but we must use one 2.
 +
 
 +
=== Solution 3 ===
 +
 
 +
''Note:  This solution uses the same strategy as Solution 1 (that having the largest possible number of three's is good), but approaches the proof in a different manner.''
 +
 
 +
Let <math>f(S) \triangleq \prod_{x \in S} x</math>, and <math>g(S) = \sum_{x\in S} x</math>, where <math>S</math> is a multiset.  We fix <math>g(S) = 1976</math>, and aim to maximize <math>f(S)</math>.  Since <math>3(x-3) > x</math> for <math>x \geq 5</math>,  we notice that <math>S</math> must only contain the  integers <math>1,2,3</math> and <math>4</math>.  We can replace any occurrences of <math>4</math> in <math>S</math> by replacing it with a couple of <math>2</math>'s, without changing <math>f(S)</math> or <math>g(S)</math>, so we may assume that <math>S</math> only contains the integers <math>1,2</math> and <math>3</math>.  We may further assume that <math>S</math> contains at most one <math>1</math>,  since any two <math>1</math>'s can be replaced by a <math>2</math> without changing <math>g(S)</math>, but with an increase in <math>f(S)</math>.  If <math>S</math> contains exactly one <math>1</math>, then it must also contain at least one <math>2</math> (since <math>1976 \equiv 2\;(\mathrm{mod }\;3)</math>).  We can then replace this pair of a <math>1</math> and a <math>2</math> with a <math>3</math>, thus keeping <math>g(S)</math> constant, and increasing <math>f(S)</math>.  Now we may assume that <math>S</math> contains only <math>2</math>'s and <math>3</math>'s. 
 +
 
 +
Now, as observed in the last solution, any triplet of <math>2</math>'s can be replaced by a couple of <math>3</math>'s, with <math>g(S)</math> constant, and an increase in <math>f(S)</math>.    Thus, after repeating this operation, we will be left with at most two <math>2</math>'s.  Since <math>g(S) = 1976</math>, and <math>1976 \equiv 2\;(\mathrm{mod }\;3)</math>,  we therefore get that <math>S</math> must have exactly one <math>2</math> (since we already showed it consists only of <math>2</math>'s and <math>3</math>'s).  Thus, we get <math>\boxed{f(S) = 2\cdot 3^{658}}</math>.
 +
 
 
== See also ==
 
== See also ==
 
{{IMO box|year=1976|num-b=3|num-a=5}}
 
{{IMO box|year=1976|num-b=3|num-a=5}}
 +
 +
[[Category:Intermediate Number Theory Problems]]

Latest revision as of 23:53, 24 May 2014

Problem

Determine the greatest number, who is the product of some positive integers, and the sum of these numbers is $1976.$

Solution

Solution 1

Since $3*3=2*2*2+1$, 3's are more efficient than 2's. We try to prove that 3's are more efficient than anything:

Let there be a positive integer $x$. If $3$ is more efficient than $x$, then $x^3<3^x$. We try to prove that all integers greater than 3 are less efficient than 3:

When $x$ increases by 1, then the RHS is multiplied by 3. The other side is multiplied by $\dfrac{(x+1)^3}{x^3}$, and we must prove that this is less than 3 for all $x$ greater than 3.

$\dfrac{(x+1)^3}{x^3}<3\Rightarrow \dfrac{x+1}{x}<\sqrt[3]{3}\Rightarrow 1<(\sqrt[3]{3}-1)x$

$\dfrac{1}{\sqrt[3]{3}-1}<x$

Thus we need to prove that $\dfrac{1}{\sqrt[3]{3}-1}<4$. Simplifying, we get $5<4\sqrt[3]{3}\Rightarrow 125<64*3=192$, which is true. Working backwards, we see that all $x$ greater than 3 are less efficient than 3, so we try to use the most 3's as possible:

$\dfrac{1976}{3}=658.6666$, so the greatest product is $\boxed{3^{658}\cdot 2}$.

Solution 2

We demonstrate heuristically that 3's are the most efficient. As we know that the chosen numbers must be equal, by the AM-GM inequality, we wish to maximize \[f(x) = \left(\frac{1976}{x}\right)^{x}\] Simple logarithmic differentiation shows that $\frac{S}{x} = e$ maximizes the given function. As $e$ is approximately 2.71828, we use 2's and 3's only. 3's are optimal, but we must use one 2.

Solution 3

Note: This solution uses the same strategy as Solution 1 (that having the largest possible number of three's is good), but approaches the proof in a different manner.

Let $f(S) \triangleq \prod_{x \in S} x$, and $g(S) = \sum_{x\in S} x$, where $S$ is a multiset. We fix $g(S) = 1976$, and aim to maximize $f(S)$. Since $3(x-3) > x$ for $x \geq 5$, we notice that $S$ must only contain the integers $1,2,3$ and $4$. We can replace any occurrences of $4$ in $S$ by replacing it with a couple of $2$'s, without changing $f(S)$ or $g(S)$, so we may assume that $S$ only contains the integers $1,2$ and $3$. We may further assume that $S$ contains at most one $1$, since any two $1$'s can be replaced by a $2$ without changing $g(S)$, but with an increase in $f(S)$. If $S$ contains exactly one $1$, then it must also contain at least one $2$ (since $1976 \equiv 2\;(\mathrm{mod }\;3)$). We can then replace this pair of a $1$ and a $2$ with a $3$, thus keeping $g(S)$ constant, and increasing $f(S)$. Now we may assume that $S$ contains only $2$'s and $3$'s.

Now, as observed in the last solution, any triplet of $2$'s can be replaced by a couple of $3$'s, with $g(S)$ constant, and an increase in $f(S)$. Thus, after repeating this operation, we will be left with at most two $2$'s. Since $g(S) = 1976$, and $1976 \equiv 2\;(\mathrm{mod }\;3)$, we therefore get that $S$ must have exactly one $2$ (since we already showed it consists only of $2$'s and $3$'s). Thus, we get $\boxed{f(S) = 2\cdot 3^{658}}$.

See also

1976 IMO (Problems) • Resources
Preceded by
Problem 3
1 2 3 4 5 6 Followed by
Problem 5
All IMO Problems and Solutions
Invalid username
Login to AoPS