Inequality from UW challenge of the week

The UW math department (students) used to have a challenge of the week where they would post high school/undergraduate level math problems.  The winner would be selected randomly from the list of correct solvers, and given a gift certificate to Baskin Robbins!

Here is one problem:

Suppose $x_1, x_2, \dots, x_n$ are real numbers such that

$$x_1 + x_2 + \dots + x_n = 0$$

and

$$x_1^2 + x_2^2 + \dots + x_n^2 = 1$$

Show that there are some $i,j$ such that $$x_i x_j \le -\frac{1}{n}$$


[Solution]