IMO 2002 SL C7

Origin: NZL | Category: Combinatorics

Problem

Among a group of 120 people, some pairs are friends. A weak quartet is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets?

Solution

For a graph G on 120 vertices (i.e., people at the party), write q(G) for the number of weak quartets in G. Our solution will consist of three parts. First, we prove that some graph G with maximal q(G) breaks up as a disjoint union of complete graphs. This will follow if we show that any two adjacent vertices x, y have the same neighbors (apart from themselves). Let Gx be the graph obtained from G by “copying” x to y (i.e., for each z ̸= x, y, we add the edge zy if zx is an edge, and delete zy if zx is not an edge). Similarly Gy is the graph obtained from G by copying y to x. We claim that 2q(G) \leqq(Gx) + q(Gy). Indeed, the number of weak quartets containing neither x nor y is the same in G, Gx, and Gy, while the number of those containing both x and y is not less in Gx and Gy than in G. Also, the number containing exactly one of x and y in Gx is at least twice the number in G containing x but not y, while the number containing exactly one of x and y in Gy is at least twice the number in G containing y but not x. This justifies our claim by adding. It follows that for an extremal graph G we must have q(G) = q(Gx) = q(Gy). Repeating the copying operation pair by pair (y to x, then their common neighbor z to both x, y, etc.) we eventually obtain an extremal graph consisting of disjoint complete graphs. Second, suppose the complete graphs in G have sizes a1, a2, . . . , an. Then

q(G) = n  i=1 ai   j<k j,k̸=i ajak. If we fix all the ai except two, say p, q, then p + q = s is fixed, and for some constants Ci, q(G) = C1+C2pq+C3

p  +
q  +C4
q
p 

• p
  q  = A + Bpq, where A and B depend only on s. Hence the maximum of q(G) is attained if |p −q| \leq1 or pq = 0. Thus if q(G) is maximal, any two nonzero ai’s differ by at most 1. Finally, if G consists of n disjoint complete graphs, then q(G) cannot exceed the value obtained if a1 = \cdot \cdot \cdot = an (not necessarily integral), which equals Qn = 1202 n 120/n n −1  = 30 \cdot 1202 (n −1)(n −2)(120 −n) n3 . It is easy to check that Qn takes its maximum when n = 5 and a1 = \cdot \cdot \cdot = a5 = 24, and that this maximum equals 15 \cdot 23 \cdot 243 = 4769280.