Difference between revisions of "1976 IMO Problems/Problem 4"
(I SOLVED AN IMO PROBLEM! :D) |
Sblnuclear17 (talk | contribs) m |
||
(8 intermediate revisions by 6 users not shown) | |||
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> | 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: | 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: | ||
Line 13: | Line 14: | ||
<math>\dfrac{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 | + | 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 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. |
<math>\dfrac{1976}{3}=658.6666</math>, so the greatest product is <math>\boxed{3^{658}\cdot 2}</math>. | <math>\dfrac{1976}{3}=658.6666</math>, so the greatest product is <math>\boxed{3^{658}\cdot 2}</math>. | ||
+ | |||
+ | ===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 <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 == |
Latest revision as of 04:29, 2 January 2023
Problem
Determine the greatest number, who is the product of some positive integers, and the sum of these numbers is
Solution 1
Since , 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 . If
is more efficient than
, then
. We try to prove that all integers greater than 3 are less efficient than 3:
When increases by 1, then the RHS is multiplied by 3. The other side is multiplied by
, and we must prove that this is less than 3 for all
greater than 3.
Thus we need to prove that . Simplifying, we get
, which is true. Working backwards, we see that all
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.
, so the greatest product is
.
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
Simple logarithmic differentiation shows that
maximizes the given function. As
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 , and
, where
is a multiset. We fix
, and aim to maximize
. Since
for
, we notice that
must only contain the integers
and
. We can replace any occurrences of
in
by replacing it with a couple of
's, without changing
or
, so we may assume that
only contains the integers
and
. We may further assume that
contains at most one
, since any two
's can be replaced by a
without changing
, but with an increase in
. If
contains exactly one
, then it must also contain at least one
(since
). We can then replace this pair of a
and a
with a
, thus keeping
constant, and increasing
. Now we may assume that
contains only
's and
's.
Now, as observed in the last solution, any triplet of 's can be replaced by a couple of
's, with
constant, and an increase in
. Thus, after repeating this operation, we will be left with at most two
's. Since
, and
, we therefore get that
must have exactly one
(since we already showed it consists only of
's and
's). Thus, we get
.
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 |