Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m
(→‎Problem)
Line 31: Line 31:
  
 
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>.
 
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>.
 +
 +
=== Solution 4 ===
 +
 +
We determine the greatest number, who is the product of some positive integers, and the sum of these numbers is <math>1976.</math>.
 +
 +
For this problem, we used induction where if we assumed that <math>i, j</math> are greater than <math>1</math>. Then
 +
<cmath>
 +
2^i \cdot 3^j > 3
 +
</cmath>
 +
where <math>k = i \cdot 2 + j \cdot 3</math>. Knowing this implies that the optimal solution comprises of twos and threes, we proceeded to show that given a configuration of
 +
<cmath>
 +
2^i \cdot 3^k,
 +
</cmath>
 +
<cmath>
 +
2^{i+n} \cdot 3^{\,j-\tfrac{2}{3}n}
 +
</cmath>
 +
is less than the original expression, implying that maximal multiplication by <math>3</math> is maximizing under the given relationship with powers of two.
 +
 +
More rigorously, we can show that maximizing with <math>3</math> is optimal by comparing the expression
 +
<cmath>
 +
2^i \cdot 3^j
 +
</cmath>
 +
with
 +
<cmath>
 +
2^{i+n} \cdot 3^{\,j-\tfrac{2}{3}n}.
 +
</cmath>
 +
Taking the ratio gives
 +
<cmath>
 +
\frac{2^{i+n} \cdot 3^{\,j-\tfrac{2}{3}n}}{2^i \cdot 3^j}
 +
= \frac{2^n}{3^{\tfrac{2}{3}n}}.
 +
</cmath>
 +
Now consider the <math>n</math>-th root of this factor:
 +
<cmath>
 +
\left(\frac{2^n}{3^{\tfrac{2}{3}n}}\right)^{\!\!1/n}
 +
= \frac{2}{3^{2/3}} < 1.
 +
</cmath>
 +
Thus multiplying by more <math>3</math>’s (rather than shifting weight into <math>2</math>’s) always gives a larger product, confirming that <math>3</math> is maximizing under the given relationship.
 +
 +
However, when we reach an edge, <math>2 \cdot 2</math> over <math>3 \cdot 1</math> is a superior solution. Given <math>1976</math> we can have
 +
<cmath>
 +
3^{658} \cdot 2.
 +
</cmath>
 +
 +
  
 
=== Video Solution by Steakmath (no algebra; basic) ===
 
=== Video Solution by Steakmath (no algebra; basic) ===

Revision as of 22:33, 26 August 2025

Problem

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


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 never use anything greater than 3. Therefore we use as many 3s in groups of 2 as possible, and since the remainder when 1976 is divided by 6 is 2, we can use 658 3s and one 2.

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

Solution 2

(Non-rigorous) 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}}$.

Solution 4

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

For this problem, we used induction where if we assumed that $i, j$ are greater than $1$. Then \[2^i \cdot 3^j > 3\] where $k = i \cdot 2 + j \cdot 3$. Knowing this implies that the optimal solution comprises of twos and threes, we proceeded to show that given a configuration of \[2^i \cdot 3^k,\] \[2^{i+n} \cdot 3^{\,j-\tfrac{2}{3}n}\] is less than the original expression, implying that maximal multiplication by $3$ is maximizing under the given relationship with powers of two.

More rigorously, we can show that maximizing with $3$ is optimal by comparing the expression \[2^i \cdot 3^j\] with \[2^{i+n} \cdot 3^{\,j-\tfrac{2}{3}n}.\] Taking the ratio gives \[\frac{2^{i+n} \cdot 3^{\,j-\tfrac{2}{3}n}}{2^i \cdot 3^j} = \frac{2^n}{3^{\tfrac{2}{3}n}}.\] Now consider the $n$-th root of this factor: \[\left(\frac{2^n}{3^{\tfrac{2}{3}n}}\right)^{\!\!1/n} = \frac{2}{3^{2/3}} < 1.\] Thus multiplying by more $3$’s (rather than shifting weight into $2$’s) always gives a larger product, confirming that $3$ is maximizing under the given relationship.

However, when we reach an edge, $2 \cdot 2$ over $3 \cdot 1$ is a superior solution. Given $1976$ we can have \[3^{658} \cdot 2.\]


Video Solution by Steakmath (no algebra; basic)

https://youtu.be/jXThxHw6RM8

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1976_IMO_Problems/Problem_4&oldid=258987"