IMO 1987 SL 2

Origin: USA

Problem

At a party attended by n married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques C1, C2, . . . , Ck with the following prop- erty: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if n \geq4, then k \geq2n.

Solution

Let di denote the number of cliques of which person i is a member. Clearly di \geq2. We now distinguish two cases: (i) For some i, di = 2. Suppose that i is a member of two cliques, Cp and Cq. Then |Cp| = |Cq| = n, since for each couple other than i and his/her spouse, one member is in Cp and one in Cq. There are thus (n −1)(n −2) pairs (r, s) of nonspouse persons distinct from i, where r \inCp, s \inCq. We observe that each such pair accounts for a different clique. Otherwise, we find two members of Cp or Cq who belong to one other clique. It follows that k \geq2 + (n−1)(n−2) \geq2n for n \geq4. (ii) For every i, di \geq3. Suppose that k < 2n. For i = 1, 2, . . . , 2n as- sign to person i an indeterminant xi, and for j = 1, 2, . . ., k set y =  i\inCj xi. From linear algebra, we know that if k < 2n, then there exist x1, x2, . . . , x2n, not all zero, such that y1 = y2 = \cdot \cdot \cdot = yk = 0. On the other hand, suppose that y1 = y2 = \cdot \cdot \cdot = yk = 0. Let M be the set of the couples and M ′ the set of all other pairs of persons. Then 0 = k  j=1 y2 j = 2n  i=1 dix2 i + 2  (i,j)\inM′ xixj

2n  i=1 (di −2)x2 i + (x1 + x2 + \cdot \cdot \cdot + x2n)2 +  (i,j)\inM (xi −xj)2 \geq 2n  i=1 x2 i > 0, if not all x1, x2, . . . , x2n are zero, which is a contradiction. Hence k \geq 2n. Remark. The condition n \geq4 is essential. For a party attended by 3 couples {(1, 4), (2, 5), (3, 6)}, there is a collection of 4 cliques satisfying the conditions: {(1, 2, 3), (3, 4, 5), (5, 6, 1), (2, 4, 6)}.