# A discrete optimization problem related to the AM-GM inequality

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.

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).
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$$.