N - 1 Equal Value Principle

The n - 1 Equal Value Principle, or n - 1 EV for short, is a useful fact regarding the optimization of sums of values of twice continuously differentiable functions with only one inflection point when the sum of the input values is constant.

Statement

Say we have $f: \mathbb{R} \rightarrow \mathbb{R}$ where $f$ is twice continuously differentiable and only has one inflection point. When $x_1, x_2, x_3, ..., x_n$ are real numbers such that $x_1 + x_2 + x_3 + ... + x_n = S$ for some constant $S$ , $f(x_1) + f(x_2) + f(x_3) + ... + f(x_n)$ is maximized or minimized only if $n-1$ of the $x$ -values are equal.

Proof

The following proof is adapted from Mildorf's Olympiad Inqeualities. $\newline$ Give me any sequence of real numbers $x$ and I show that my sequence, with $n-1$ equal terms, gives a greater or equal result. (Obviously, similar reasoning applies when minimizing the sum.) $\newline$ WLOG assume that for some value $k$ , $f$ 's inflection point, $f$ is convex for values below and at $k$ and concave otherwise and at $k$ . Also assume that $x$ are non-increasing. Now, define $m$ so that $x_1 \geq ... \geq x_m \geq k \geq x_{m+1} \geq ... \geq x_n$ . $\newline$ Since $(x_1, ..., x_m) \prec (x_1 + ... + x_m - (m - 1)k, k, ..., k)$ and $f$ is convex below and at $k$ , we can apply Karamata's Inequality to obtain: $\newline$ $f(x_1) + ... + f(x_m) \leq f(x_1 + ... + x_m - (m - 1)k) + (m - 1)f(k)$ $\newline$ Since $(k, ..., k, x_{m + 1}, ..., x_n) \succ (\frac{(m-1)k + x_{m + 1} + ... + x_n}{n-1}, ..., \frac{(m-1)k + x_{m + 1} + ... + x_n}{n-1})$ and f is concave (as opposed to convex) above and at $k$ , we can apply Karamata's Inequality once more to obtain: $\newline$ $f(k) + ... + f(k) + f(x_{m + 1}) + ... + f(x_n) \leq (n-1)f(\frac{(m - 1)k + x_{m + 1} + ... + x_n}{n - 1}))$ $\newline$ Finally, by the transitive property, $\newline$ $f(x_1) + ... + f(x_n) \leq f(x_1 + ... + x_m - (m - 1)k) + (n - 1)f(\frac{(m - 1)k + x_{m + 1} + ... + x_n}{n - 1})$ $\newline$ as desired. $\newline$ The following video by Evan Chen may be a helpful aid in understanding this technique: https://www.youtube.com/watch?v=Kkhuk8GiuOU

Page

Toolbox

Search

N - 1 Equal Value Principle

Statement

Proof