Generalizing a Math Problem

Consider the following problem:

Find distinct positive integers that add up to and have the maximum product.

— Singapore Mathematical Olympiad, 2005

If the integers are non-distinct, the integers are , due to the AM-GM inequality.

For real numbers ,

with equality if and only if .

Intuitively, the integers should be as close to each other as possible for the maximum product if they have the same sum.

For a pair of integers, this can be proven by the quadratic equation:

So must be minimized for to be maximized. Also,

Which makes the minimum difference between consecutive integers if their sum is odd, and if their sum is even.

Alternatively, it might be easier to visualize by considering the odd and even cases separately.
Sum is odd:

Sum is even:

So for integers, , the difference between and is either or , and the difference between and is either or .
We can manually check each possible permutation:

Generalizing the problem

Hmm, is there a better way than manually checking every possible permutation?

Can we solve the generalized problem:

Find distinct positive integers that add up to and have the maximum product.

If we were to manually check each permutation, we would have to check permutations!

Lemma: There can be at most pair of consecutive integers with a difference of .

Let the distinct integers be where . There can only be at most one where and . For every other where and , .

Suppose there are distinct pairs of consecutive integers with and where . Let , , , .

Consider the pair and .
The current difference is .
Keeping the sum the same at , we can change to and to .
The new difference is .
Since the new difference is smaller, the new product is larger.
With the new changes, and .

Hence, the sequence cannot have pairs of consecutive integers with a difference of , so it has at most pair of consecutive integers with a difference of (with all other pairs of consecutive integers having a difference of ).

We can enumerate all such unique sequences, and show that the sum is strictly increasing by and hence unique.

If there exists a pair of consecutive integers that has a difference of , and we can add to the first integer in that pair.
Else, we can add to the last integer to create a pair with a difference of .

If is odd:

If is even:

Generalizing the solution further

Surprisingly, we can use the solution to solve the much more general problem:

Find distinct positive integers that add up to and have the maximum product.

Similarly,

If is odd:

If is even:

Credits

Massive thanks to Joel Yip for helping with the problem and solution!