Using Symmetry – Mattia Giuri's bizarre blog

I put this problem in an old team competition I organized. It is not simple, and I asked only for the case where n is even, now I’ll show you the complete version.

Let $x_1, x_2, ..., x_n$ be reals in an interval $[a, a+1]$ of lenght 1. Find the maximum value of

$f = \frac{1}{n}\sum_{i=1}^{n}x_i^2 - (\frac{1}{n}\sum_{i=1}^{n}x_i)^2$

Now, let’s treat $x_2, ..., x_n$ as constants and let $x_1$ be the variable.

We notice

$\frac{n-1}{n^2}x_1^2 - (\frac{2}{n^2}\sum_{i=2}^{n}x_i)x_1 + \frac{1}{n}\sum_{i=2}^{n}x_i^2 - (\frac{1}{n}\sum_{i=2}^{n}x_i)^2$

This is a quadratic function and the coefficient of the quadratic term is positive.

Since the function is convex, the maximum is reached at $x_1=a$ or at $x_1 = a+1$ .

By symmetry, we can apply the same reasoning to all the numbers. Hence let’s say that we have r terms equal to a and n-r terms equal to a+1.

We have that the maximum is:

$\frac{1}{n}[ra^2+(n-r)(a+1)^2]-\frac{1}{n^2}[ra+(n-r)(a+1)]^2$

Expanding and simplifying leads to:

$\frac{1}{n^2}r(n-r)$

The product of two numbers with constant sum is maximum when their difference is minimal. Hence, the maximum is:

$\begin{cases} \frac{1}{n^2} \cdot (\frac{n}{2})^2 = \frac{1}{4}, & \mbox{if } n \mbox{ is even} \\ \frac{1}{n^2} \cdot \frac{n+1}{2}\frac{n-1}{2} = \frac{n^2-1}{4n^2}, & \mbox{if } n \mbox{ is odd} \end{cases}$