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

Latest revision as of 03:29, 2 January 2023

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

@@ Line 2: / Line 2: @@
 Determine the greatest number, who is the product of some positive integers, and the sum of these numbers is <math>1976.</math>
-== 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:

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

Page

Toolbox

Search