IMO 1976 Problem 4

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 5m33s

Problem

Find the largest number obtainable as the product of positive integers whose sum is $1976$.

Exploration

A product of positive integers with fixed sum increases when the summands are replaced by a partition that favors factors close to the maximizer of the function $x \mapsto x^{1/x}$. Testing small decompositions shows that $3$ contributes more to the product than $2$ or $4$ when replacing larger integers, while $1$ is always detrimental since it reduces product without improving any other factor.

For instance, replacing $5$ by $2+3$ preserves the sum and increases the product since $2 \cdot 3 = 6$ exceeds $5$. Similarly, replacing $4$ by $2+2$ preserves the sum and increases the product since $2 \cdot 2 = 4$ equals $4$, and in larger configurations the distribution into $3$’s yields higher growth.

The structure therefore suggests an optimal partition consisting almost entirely of $3$’s, with adjustments depending on the remainder when $1976$ is divided by $3$.

The key difficulty is ensuring that every possible integer partition can be systematically transformed into one using only $2$’s and $3$’s without decreasing the product, and then determining the precise optimal combination of these.

Problem Understanding

This is a Type C problem. One must determine the maximum possible product of positive integers whose sum is fixed at $1976$.

The structure of the problem indicates a constrained integer optimization problem: among all partitions of $1976$, identify the one that maximizes the multiplicative value of its parts. The natural expectation is that the optimal configuration uses as many $3$’s as possible, since $3$ balances being large while still contributing efficiently to product growth.

The core difficulty is proving that no partition involving integers larger than $3$, or involving too many $2$’s or $1$’s, can exceed the product obtained from the optimal combination of $3$’s with a small correction depending on the remainder modulo $3$.

The expected answer is

$$2 \cdot 3^{658},$$

since $1976 = 3 \cdot 658 + 2$.

Proof Architecture

Lemma 1 asserts that any integer partition containing a part at least $5$ can be modified by replacing that part with smaller positive integers whose sum is equal but whose product is strictly larger. The justification comes from explicit comparison $n < 3(n-3)$ for $n \ge 5$, ensuring improvement via replacement.

Lemma 2 asserts that the part $4$ can be replaced by $2+2$ without changing the product, allowing normalization of all partitions into parts only $2$ and $3$ without decreasing the product.

Lemma 3 asserts that any occurrence of $1$ in a partition can be absorbed into another part without decreasing the sum while strictly increasing the product, since $1$ reduces multiplicative value without compensating gain.

Lemma 4 asserts that among partitions using only $2$ and $3$, the product is maximized by using as many $3$’s as possible, with the only adjustment occurring when the remaining sum is $2$ or $4$.

The most delicate part is Lemma 1, since it must guarantee a strict improvement for all integers at least $5$.

Solution

Lemma 1

If $n \ge 5$, then $n < 3(n-3)$.

For $n \ge 5$, computation gives

$$3(n-3) - n = 3n - 9 - n = 2n - 9.$$

For $n = 5$, this equals $1$, and for $n = 6$, it equals $3$. For all $n \ge 5$, the expression $2n - 9$ is positive, hence $3(n-3) > n$. Replacing a part $n$ by $3$ and $n-3$ preserves the sum and increases the product since $3(n-3) > n$.

This establishes that any part at least $5$ can be eliminated in favor of smaller parts with strictly larger product, preventing optimal partitions from containing integers exceeding $4$.

Lemma 2

Replacing $4$ by $2+2$ preserves product and sum.

Direct computation gives $2 \cdot 2 = 4$, so any occurrence of $4$ can be replaced without changing the product, while maintaining the same total sum. This permits restricting attention to partitions using only $2$ and $3$.

Lemma 3

Any occurrence of $1$ can be removed in favor of increasing another part while increasing product.

If a partition contains $1$ and another part $k$, replacing $1+k$ by $k+1$ does not change the sum. The product comparison gives

$$1 \cdot k = k < k+1,$$

so the transformation strictly increases the product. Thus no optimal partition contains $1$.

Lemma 4

Among partitions of $1976$ using only $2$ and $3$, the product is maximized by maximizing the number of $3$’s subject to the sum constraint.

Any partition into $2$’s and $3$’s with the same sum differs by trading $2+2+2$ with $3+3$. The product comparison is

$$2 \cdot 2 \cdot 2 = 8 < 9 = 3 \cdot 3,$$

so replacing three $2$’s by two $3$’s increases product. Iterating this replacement reduces the number of $2$’s as much as possible, leaving at most one or two $2$’s depending on the residue of the total sum modulo $3$.

This establishes that optimal structure uses as many $3$’s as possible with minimal adjustment.

Main argument

From Lemmas 1, 2, and 3, any optimal partition of $1976$ can be transformed into a partition consisting only of $2$ and $3$ without decreasing the product.

Let the number of $3$’s be $a$ and the number of $2$’s be $b$. Then

$$3a + 2b = 1976.$$

Maximization requires minimizing $b$ while preserving the sum modulo $3$. Since $1976 \equiv 2 \pmod{3}$, the representation with the largest possible number of $3$’s is obtained by taking $b = 1$, because

$$1976 - 2 = 1974$$

and $1974$ is divisible by $3$, giving

$$a = 658.$$

Thus the optimal partition is $658$ copies of $3$ and one copy of $2$, producing product

$$2 \cdot 3^{658}.$$

This configuration is achievable and, by Lemma 4, no other arrangement of $2$’s and $3$’s yields a larger product.

Therefore the maximum product is

$$\boxed{2 \cdot 3^{658}}.$$

Verification of Key Steps

The transition from a general partition to one involving only $2$ and $3$ relies on repeated replacement of large integers using Lemma 1 and elimination of $4$ and $1$ using Lemmas 2 and 3. A failure mode would occur if a replacement increased the number of parts in a way that invalidates monotonic improvement; however, each transformation preserves sum exactly while strictly increasing or maintaining product, ensuring global improvement at each step.

The comparison $2 \cdot 2 \cdot 2 < 3 \cdot 3$ is decisive for eliminating excess $2$’s. A careless argument might assume local improvements always extend globally, but here every replacement acts on disjoint subcollections, ensuring no interaction effects.

The modular constraint $1976 \equiv 2 \pmod{3}$ determines the unavoidable presence of a single $2$ in the optimal configuration, since any attempt to remove it would force inclusion of a $1$ or reduce a $3$ to smaller parts, both of which reduce product.

Alternative Approaches

A different approach uses the concavity of the logarithm function to transform the problem into maximizing a sum of logarithms under a linear constraint, leading to a continuous relaxation whose optimizer occurs at $x = 3$. Discretization then forces the same partition structure into $2$’s and $3$’s.

Another approach uses repeated smoothing of partitions by replacing any pair $(a,b)$ with $(a+1,b-1)$ or vice versa and tracking the effect on the product, eventually converging to the same extremal structure dominated by $3$’s.