Using Symmetry

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}

Scroll to top