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 16: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 |