1976 IMO Problems/Problem 4
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 |