IMO 1976 SL 10

Origin: USA

Problem

Find the largest number obtainable as the product of pos- itive integers whose sum is 1976.

Solution

Let a1 < a2 < \cdot \cdot \cdot < an be positive integers whose sum is 1976. Let M denote the maximal value of a1a2 \cdot \cdot \cdot an. We make the following observa- tions: (1) a1 = 1 does not yield the maximum, since replacing 1, a2 by 1 + a2 increases the product. (2) aj −ai \geq2 does not yield the maximal value, since replacing ai, aj by ai + 1, aj −1 increases the product. (3) ai \geq5 does not yield the maximal value, since 2(ai−2) = 2ai−4 > ai. Since 4 = 22, we may assume that all ai are either 2 or 3, and M = 2k3l, where 2k + 3l = 1976. (4) k \geq3 does not yield the maximal value, since 2 \cdot 2 \cdot 2 < 3 \cdot 3. Hence k \leq2 and 2k \equiv1976 (mod 3) gives us k = 1, l = 658 and M = 2 \cdot 3658.