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 never use anything greater than 3. Therefore we use as many 3s in groups of 2 as possible, and since the remainder when 1976 is divided by 6 is 2, we can use 658 3s and one 2.
, so the greatest product is .
(Non-rigorous) 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.
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 .
|1976 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|