Difference between revisions of "1976 IMO Problems/Problem 4"
(made it prettier) |
Mapletree14 (talk | contribs) (→Solution) |
||
Line 18: | Line 18: | ||
<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 === | + | ===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. | ||
− | ''Note: This solution uses the same strategy as | + | === 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 = 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. | 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 = 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 = 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 = 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 == |
Revision as of 11:45, 30 July 2013
Problem
Determine the greatest number, who is the product of some positive integers, and the sum of these numbers is
Solution
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 try to use the most 3's as possible:
, so the greatest product is
.
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
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 |