Putnam 1968/A4 solution

29th Putnam 1968

Problem A4

Let S₂ be the 2-sphere { (x, y, z) : x² + y² + z² = 1}. Show that for any n points on S₂, the sum of the squares of the n(n - 1)/2 distances between them (measured in space, not in S₂) is at most n².

Solution

Let the points be (x_i, y_i, z_i) for i = 1, 2, ... n. The square of the distance between the pair i, j is (x_i - x_j)² + (y_i - y_j)² + (z_i - z_j)² = (x_i² + y_i² + z_i²) + (x_j² + y_j² + z_j²) - 2(x_ix_j + y_iy_j + z_iz_j) = 2 - 2 (x_ix_j + y_iy_j + z_iz_j). Hence the sum of the squares of the distances is n(n-1) - 2 ∑ (x_ix_j + y_iy_j + z_iz_j).

Now (x₁ + x₂ + ... + x_n)² = ∑ x_i² + 2 ∑ x_ix_j. So 2 ∑ (x_ix_j + y_iy_j + z_iz_j) = X² + Y² + Z² - ∑ (x_i² + y_i² + z_i²) = X² + Y² + Z² - n, where X = ∑ x_i, Y = S y_i, Z = ∑ z_i. Hence the sum of the squares is n² - (X² + Y² + Z²), which is at most n².

[Playing with small examples it is tempting to think that the maximum is only achieved when the points are symmetrically distributed, eg at the vertices of a triangle or tetrahedron, but the result shows that this is not true. For n even, for example, we can take the points in diametrically opposite pairs, but otherwise random.]

29th Putnam 1968