# Find the maximal value of the product

If $n_1,n_2,\ldots,n_k$ are natural numbers and $n_1+n_2+\cdots+n_k = n$, show $$\max_{n_1+\cdots+n_k = n} n_1n_2 \cdots n_k = (t+1)^r t^{k-r},$$ where $t = \left[\dfrac{n}{k}\right]$ and $r$ is the remainder upon division by $k$; i.e., $n = tk+r$, $0\leq r \leq k-1$.

If $\dfrac{n}{k}$ is an integer then we can just use AM-GM to deduce that we must have $n_1 = \cdots = n_k$ for the maximal value, which is $t^k$. What if $\dfrac{n}{k}$ is not an integer?

First note that given $n_1, \ldots, n_k$ with $n_1 \ldots n_k$ maximizied we have $| n_i - n_j | \leq 1$. Otherwise (up to reordering) we have $n_j - n_i - 1 > 0$ and $(n_i + 1)(n_j - 1) - n_i n_j = n_j - n_i -1 > 0$, so subbing the pair $(n_i, n_j)$ for $(n_i + 1, n_j - 1)$ increases the total product.
A list of $k$ integers which pairwise are at most one apart must in fact only contain 2 distinct integers which themselves are at most one apart. Call these $t$ and $t+1$. Thus our optimal arrangement has some number of $t$'s and $t+1$'s, let's say $r$ of them are $t+1$ and $k-r$ are $t$. (At this point we do not know which integers are $t$ and $r$). For these integers to be feasible we must have them sum to $n$, so we get $k t + r = n$. From this we conclude in fact $t = [n/k]$ and $r$ is the remainder.
• Can you explain how we have the first $r$ are $t+1$ and the last $k-r$ are $t$? Sep 30 '16 at 0:32
• If all the numbers are at most 1 apart, then there can only be two distinct integers that show up in the list, and they are one apart. Thus we conclude the integers are all $t$ and $t +1$, where we don't know what $t$ are. We then add these up to show what $t$ is. Sep 30 '16 at 0:35
• But how do you know how many are $t+1$ and how many are $t$? Sep 30 '16 at 0:40
• I edited my response to hopefully make the second part more clear. The point is that we first can conclude that the only integers in our list are $t$ and $t+1$ for some $t$, then call the number of $t+1$'s $r$. We then use the fact they sum to $n$ to determine $t$ and $r$. Sep 30 '16 at 0:45