IMO 1998 SL 25

Origin: NZL

Problem

Let U = {1, 2, . . ., n}, where n \geq3. A subset S of U is said to be split by an arrangement of the elements of U if an element not in S occurs in the arrangement somewhere between two elements of S. For example, 13542 splits {1, 2, 3} but not {3, 4, 5}. Prove that for any n −2 subsets of U, each containing at least 2 and at most n −1 elements, there is an arrangement of the elements of U that splits all of them.

Solution

We use induction on n. For n = 3, we have a single two-element subset {i, j} that is split by (i, k, j) (where k is the third element of U). Assume that the result holds for some n \geq3, and consider a family F of n −1 proper subsets of U = {1, 2, . . ., n + 1}, each with at least 2 elements. To continue the induction, we need an element a \inU that is contained in all n-element subsets of F, but in at most one of the two-element subsets. We claim that such an a exists. Let F contain k n-element subsets and m 2-element subsets (k + m \leqn −1). The intersection of the n-element subsets contains exactly n + 1 −k \geqm + 2 elements. On the other hand, at most m elements belong to more than one 2-element subset, which justifies our claim.

Now let A be the 2-element subset that contains a, if it exists; otherwise, let A be any subset from F containing a. Excluding a from all the subsets from F \ {A}, we get at most n −2 subsets of U \ {a} with at least 2 and at most n −1 elements. By the inductive hypothesis, we can arrange U \ {a} so that we split all the subsets of F except A. It remains to place a, and we shall make a desired arrangement if we put it anywhere away from A.