11
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

11
$\begingroup$

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

$\endgroup$
2
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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