IMO 1986 SL 8

Origin: USA

Problem

From a collection of n persons q distinct two-member teams are selected and ranked 1, . . . , q (no ties). Let m be the least integer larger than or equal to 2q/n. Show that there are m distinct teams that may be listed so that (i) each pair of consecutive teams on the list have one member in common and (ii) the chain of teams on the list are in rank order. Alternative formulation. Given a graph with n vertices and q edges num- bered 1, . . . , q, show that there exists a chain of m edges, m \geq2q n , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.

Solution

We shall solve the problem in the alternative formulation. Let LG(v) de- note the length of the longest directed chain of edges in the given graph G that begins in a vertex v and is arranged decreasingly relative to the num- bering. By the pigeonhole principle it suffices to show that  v L(v) \geq2q in every such graph. We do this by induction on q. For q = 1 the claim is obvious. We assume that it is true for q −1 and consider a graph G with q edges numbered 1, . . . , q. Let the edge number q connect vertices u and w. Removing this edge, we get a graph G′ with q −1 edges. We then have LG(u) \geqLG′(w) + 1, LG(w) \geqLG′(u) + 1, LG(v) \geqLG′(v) for other v. Since  LG′(v) \geq2(q −1) by inductive assumption, it follows that  LG(v) \geq2(q −1) + 2 = 2q as desired. Second solution. Let us place a spider at each vertex of the graph. Let us now interchange the positions of the two spiders at the endpoints of each edge, listing the edges increasingly with respect to the numbering. This way we will move spiders exactly 2q times (two for each edge). Hence there is a spider that will be moved at least 2q/n times. All that remains is to notice that the path of each spider consists of edges numbered in increasing order. Remark. A chain of the stated length having all vertices distinct does not necessarily exist. An example is n = 4, q = 6 with the numbering following the order ab, cd, ac, bd, ad, bc.