How to minimise the maximum value of a variable given an equation.

Question

I have an equation $$x + y + z = n$$ I want to minimize the $\max\{x,y,z\}$.

From my intuition, it is clear that the maximum will be minimized when $x=y=z$. But how can I prove it mathematically?

Answer 1

The function $f(x) = \max_k x_k$ is convex, and the set $F = \{ x | \sum_k x_k = n \}$ is convex.

Note that $f(x) = f(Px)$ for any permutation $P$ (and $P F = F$).

Let ${\cal P}$ be the set of permutations of the indices of $x$.

Since $f$ is convex, we have $f( {1 \over |{\cal P}|}\sum_{P \in {\cal P}} Px ) = f(\bar{x}) \le {1 \over |{\cal P}|} \sum_{P \in {\cal P}} f(Px) = f(x)$, where $\bar{x} = {1 \over |{\cal P}|}\sum_{P \in {\cal P}} Px = ({1 \over n}\sum_k x_k) (1,...,1)$.

Since $\sum_k x_k = n$, we see that $f$ is minimised on $F$ at $(1,...,1)$.

Simpler approach:

The pigeon hole principle shows that if $x \in F$, then there is some $k$ such that $x_k \ge 1$. Hence $f(x) \ge 1$ for all $x \in F$. Since $f((1,...,1)) = 1$, we see that $(1,...,1)$ is a (the) minimiser of $f$ on $F$.