IMO 2012 Shortlist C7

Category: Combinatorics

Problem

There are given 2500 points on a circle labeled 1,2,...,2500 in some order. Prove that one can choose 100 pairwise disjoint chords joining some of these points so that the 100 sums of the pairs of numbers at the endpoints of the chosen chords are equal. Solution. The proof is based on the following general fact. Lemma. In a graph G each vertex v has degree dv. Then G contains an independent set S of vertices such that |S| ≥ f(G) where f(G) = X v∈G dv + 1 . Proof. Induction on n = |G|. The base n = 1 is clear. For the inductive step choose a vertex v0 in G of minimum degree d. Delete v0 and all of its neighbors v1,...,vd and also all edges with endpoints v0,v1,...,vd. This gives a new graph G′ . By the inductive assumption G′ contains an independent set S′ of vertices such that |S′ | ≥ f(G′ ). Since no vertex in S′ is a neighbor of v0 in G, the set S = S′ ∪ {v0} is independent in G. Let d′ v be the degree of a vertex v in G′ . Clearly d′ v ≤ dv for every such vertex v, and also dvi ≥ d for all i = 0,1,...,d by the minimal choice of v0. Therefore f(G′ ) = X v∈G′ d′ v + 1 ≥ X v∈G′ dv + 1 = f(G) − d X i=0 dvi

1 ≥ f(G) − d + 1 d + 1 = f(G) − 1. Hence |S| = |S′ | + 1 ≥ f(G′ ) + 1 ≥ f(G), and the induction is complete. We pass on to our problem. For clarity denote n = 2499 and draw all chords determined by the given 2n points. Color each chord with one of the colors 3,4,...,4n − 1 according to the sum of the numbers at its endpoints. Chords with a common endpoint have different colors. For each color c consider the following graph Gc. Its vertices are the chords of color c, and two chords are neighbors in Gc if they intersect. Let f(Gc) have the same meaning as in the lemma for all graphs Gc. Every chord ℓ divides the circle into two arcs, and one of them contains m(ℓ) ≤ n−1 given points. (In particular m(ℓ) = 0 if ℓ joins two consecutive points.) For each i = 0,1,...,n − 2 there are 2n chords ℓ with m(ℓ) = i. Such a chord has degree at most i in the respective graph. Indeed let A1,...,Ai be all points on either arc determined by a chord ℓ with m(ℓ) = i and color c. Every Aj is an endpoint of at most 1 chord colored c, j = 1,...,i. Hence at most i chords of color c intersect ℓ. It follows that for each i = 0,1,...,n − 2 the 2n chords ℓ with m(ℓ) = i contribute at least 2n i+1 to the sum P c f(Gc). Summation over i = 0,1,...,n − 2 gives X c f(Gc) ≥ 2n n−1 X i=1 i . Because there are 4n − 3 colors in all, averaging yields a color c such that f(Gc) ≥ 2n 4n − 3 n−1 X i=1 i

n−1 X i=1 i . By the lemma there are at least 1 Pn−1 i=1 i pairwise disjoint chords of color c, i. e. with the same sum c of the pairs of numbers at their endpoints. It remains to show that 1 Pn−1 i=1 i ≥ 100 for n = 2499 . Indeed we have n−1 X i=1 i

X i=1 i = 1 + 400 X k=1 2k X i=2k−1+1 i

1 + 400 X k=1 2k−1 2k = 201 > 200. This completes the solution.29