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.

  • $\begingroup$ Can you explain how we have the first $r$ are $t+1$ and the last $k-r$ are $t$? $\endgroup$ Sep 30 '16 at 0:32
  • $\begingroup$ 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. $\endgroup$
    – Nick R
    Sep 30 '16 at 0:35
  • $\begingroup$ But how do you know how many are $t+1$ and how many are $t$? $\endgroup$ Sep 30 '16 at 0:40
  • $\begingroup$ 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$. $\endgroup$
    – Nick R
    Sep 30 '16 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.