IMO 2001 SL C3

Origin: RUS | Category: Combinatorics

Problem

Define a k-clique to be a set of k people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

Solution

Consider one such party. The result is trivially true if there is only one 3-clique, so suppose there exist at least two 3-cliques C1 and C2. We distinguish two cases: (i) C1 = {a, b, c} and C2 = {a, d, e} for some distinct people a, b, c, d, e. If the departure of a destroys all 3-cliques, then we are done. Otherwise, there is a third 3-clique C3, which has a person in common with each of C1, C2 and does not include a: say, C3 = {b, d, f} for some f. We thus obtain another 3-clique C4 = {a, b, d}, which has two persons in common with C3, and the case (ii) is applied. (ii) C1 = {a, b, c} and C2 = {a, b, d} for distinct people a, b, c, d. If the departure of a, b leaves no 3-clique, then we are done. Otherwise, for some e there is a clique {c, d, e}. We claim that then the departure of c, d breaks all 3-cliques. Sup- pose the opposite, that a 3-clique C remains. Since C shares a per- son with each of the 3-cliques {c, d, a}, {c, d, b}, {c, d, e}, it must be C = {a, b, e}. However, then {a, b, c, d, e} is a 5-clique, which is as- sumed to be impossible.