Difference between revisions of "1976 IMO Problems/Problem 4"
(Slightly differnt solution) |
(made it prettier) |
||
Line 3: | Line 3: | ||
== Solution == | == 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 17: | 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 === |
''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.'' | ''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.'' |
Revision as of 00:25, 21 May 2012
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
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 |