1976 IMO Problems/Problem 4
Determine the greatest number, who is the product of some positive integers, and the sum of these numbers is
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 .
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 .
|1976 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|