IMO shortlist 1985/28 solution

26th IMO 1985 shortlist

Problem 28

X is the set {1, 2, ... , n}. P₁, P₂, ... , P_n are distinct pairs of elements of X. P_i and P_j have an element in common iff {i, j} is one of the pairs. Show that every element of X belongs to exactly two of the pairs.

Solution

Solution by Demetres Christofides

Suppose that i appears in a_i of the pairs. Counting pairs, we have 2n = a₁ + a₂ + ... + a_n. If two pairs both contain i, then they do not have any other element in common. So the a_i pairs containing i give rise to a_i(a_i - 1)/2 pairs with i as common element. Thus the number of pairs is also ∑ a_i(a_i - 1)/2. So ∑ a_i(a_i - 1) = 2n. Hence ∑ a_i² = 4n. But, by Cauchy Schwartz, 4n² = (∑ 1 a_i)² ≤ (∑ 1²)(∑ a_i²) = 4n² with equality iff all a_i are equal and hence iff all a_i = 2.

26th IMO shortlist 1985