A discrete optimization problem related to the AM-GM inequality

Question

Let $k\in\mathbb{Z}_{>0}$, and $s\in\mathbb{N}$, and for $m_1,\ldots,m_k$ some nonnegative integers, consider the problem of maximizing the product $$ (1+m_1)(1+m_2)\cdots(1+m_k) $$ under the constraint $m_1+\cdots+m_k=s$.

I would like to know:

1. The exact formula $M(k,s)$ for the maximal value of the product.
2. A complete description of the tuples $(m_1,\ldots,m_k)$ which achieve the maximum.

Of course with the $m_i$ taking continuous real values, this is just the equality case of the arithmetic mean-geometric mean inequality and maximization calls for $m_i$'s that are "as equal to each other as possible", but forcing integer values makes this rather messy.

I can try to work my way through this, but it would feel like reinventing the wheel. A solution to 1. and 2. or pointer to the relevant literature would be appreciated.

Answer 1

This was essentially answered by Nate in the comments, but here are some more details. As Nate argues, $|m_i - m_j| \leq 1$ for all distinct $i,j$. Thus, if $s=ak+r$, where $a,r \in \mathbb{N}$ and $r < k$, then there is a unique choice (up to permuting variables) which maximizes the product. Namely, set $r$ of the variables to $\lceil s/k \rceil$ and the rest to $\lfloor s/k \rfloor$.

This problem is related to Turán's Theorem, which concerns the maximum possible number of edges in a graph on $s$ vertices with no $K_{k+1}$ subgraph. The answer is given by the Turán graph, which is unique. More generally, Zykov proved that among $K_{k+1}$-free graphs, the Turán graph also has the most number of complete graphs $K_t$ for all $t \leq k$. The case $t=k$ leads to your optimization problem (once you have already established that such a graph must be $k$-partite).

Answer 2

Converted from a comment by user Nate:

If two of them have difference at least 2 say $m_i - m_j > 2$ then replacing $m_i$ with $m_{i} - 1$ and $m_j$ with $m_{i} + 1$ increases the value of the product. So for a maximal choice the $m_i$'s can only take values $a$ and $a+1$ where $a = \lfloor s/k \rfloor$.