Generalizing a Math Problem

Consider the following problem:

Find $3$ distinct positive integers that add up to $3n$ and have the maximum product.
$n\in {\mathbb{Z}}^{+}$
-- Singapore Mathematical Olympiad, 2005

If the integers are non-distinct, the $3$ integers are $\{n,n,n\}$, due to the AM-GM inequality.

For $3$ real numbers $a,b,c\ge 0$,

with equality if and only if $a=b=c$.

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 $|b-c|$ must be minimized for $bc$ to be maximized. Also,

Which makes the minimum difference between $2$ consecutive integers $1$ if their sum is odd, and $2$ 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 $3$ integers, $a<b<c$, the difference between $a$ and $b$ is either $1$ or $2$, and the difference between $b$ and $c$ is either $1$ or $2$.
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 $m$ distinct positive integers that add up to $mn$ and have the maximum product.
$n,m\in {\mathbb{Z}}^{+}$

If we were to manually check each permutation, we would have to check $2^{m-1}$ permutations!

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

Let the $m$ distinct integers be $a_1,a_2,...,a_m$ where $a_1<a_2<...<a_m$. There can only be at most one $i$ where $a_{i+1}-a_i=2$ and $1\le i<m$. For every other $j$ where $1\le j<m$ and $j\ne i$, $a_{j+1}-a_j=1$.

Suppose there are $2$ distinct pairs of consecutive integers with $a_{i+1}-a_i=2$ and $a_{j+1}-a_j=2$ where $1<i<j<m$. Let $a_i=x$, $a_{i+1}=x+2$, $a_j=y$, $a_{j+1}=y+2$.

Consider the pair $a_i=x$ and $a_{j+1}=y+2$.
The current difference is $a_{j+1}-a_i=y+2-x$.
Keeping the sum the same at $a_i+a_{j+1}=x+y+2$, we can change $a_i$ to $x+1$ and $a_{j+1}$ to $y+1$.
The new difference is $a_{j+1}-a_i=y-x<y+2-x$.
Since the new difference is smaller, the new product $a_i{a}_{j+1}$ is larger.
With the new changes, $a_{i+1}-a_i=1$ and $a_{j+1}-a_j=1$.

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

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

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

If $m$ is odd:

If $m$ is even:

#Generalizing the solution further

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

Find $m$ distinct positive integers that add up to $s$ and have the maximum product.
$m,s\in {\mathbb{Z}}^{+},s\ge \frac{m(m+1)}{2}$

Similarly,

If $m$ is odd:

If $m$ is even:

#Credits

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