0
$\begingroup$

Let $S$ be a fixed integer satisfying $S \ge 1$, let $a$ range over the integers between $1$ and $S$ inclusive, and for $i = 1, \dotsc, a$, let each $x_i$ range over the nonnegative integers, such that the $x_1 + \dotsc + x_a = S$ will be a partition of $S$.

Consider the discrete, constrained optimization problem defined by: $$f(a; S) = \max\limits_{\{ x_i\}}\Bigl[ \ln\big( \prod\limits_{i = 1}^{a} x_i \bigr) \colon \;\sum\limits_i^{a} x_i = S \Bigr]$$

It is straightforward to determine the explicit value of $f(a; S)$ in terms of the floor $\lfloor \tfrac{S}{a} \rfloor$. Basically, the $x_i$ have to be as uniform as possible while remaining positive integers summing to $S$.

Intuition and numerical evidence suggest that $f(a;S)$ is discretely concave with respect to $a$, in the sense that $$ f(a; S) \ge \tfrac{1}{2} f(a-1; S) + \tfrac{1}{2} f(a+1; S) $$ for all integers $a$ in the range $1 < a <S$.

Can anyone suggest a simple proof of this fact? It is easy to show via Jensen's inequality that $f(a; S)$ lies below the concave function $a \ln (S/a)$, but that of course is not enough. Induction on $S$ does not appear terribly promising.

$\endgroup$
0
$\begingroup$

No sooner did I submit this than I realized that there is indeed a simple answer:

Note that $f(2a; 2S) = 2 f(a;S)$. But by writing $2S = S + S$ and partitioning one $S$ into a sum of $(a-1)$ terms and the other into a sum of $(a+1)$ terms, because $f(2a,2S)$ is defined as an optimum, we see that $f(2a, 2S) \ge f(a-1, S) + f(a+1, S)$.

$\endgroup$

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.