Difference between revisions of "1976 IMO Problems/Problem 4"
(I SOLVED AN IMO PROBLEM! :D) |
(Slightly differnt solution) |
||
Line 16: | Line 16: | ||
<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>. | ||
+ | |||
+ | ==Alternate Solution== | ||
+ | |||
+ | ''Note: This solution uses the same strategy as the above solution (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. | ||
+ | |||
+ | 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 17:27, 20 May 2012
Problem
Determine the greatest number, who is the product of some positive integers, and the sum of these numbers is
Solution
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
.
Alternate Solution
Note: This solution uses the same strategy as the above solution (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 |