IMO 1978 SL 1

Origin: BUL

Problem

The set M = {1, 2, . . ., 2n} is partitioned into k nonintersecting subsets M1, M2, . . . , Mk, where n \geqk3 + k. Prove that there exist even numbers 2j1, 2j2, . . . , 2jk+1 in M that are in one and the same subset Mi (1 \leqi \leqk) such that the numbers 2j1 −1, 2j2 −1, . . . , 2jk+1 −1 are also in one and the same subset Mj (1 \leqj \leqk).

Solution

There exists an Ms that contains at least 2n/k = 2(k2 + 1) elements. It follows that Ms contains either at least k2 + 1 even numbers or at least k2 +1 odd numbers. In the former case, consider the predecessors of those k2 +1 numbers: among them, at least k2+1 k+1 > k, i.e., at least k +1, belong to the same subset, say Mt. Then we choose s, t. The latter case is similar. Second solution. For all i, j \in{1, 2, . . ., k}, consider the set Nij = {r | 2r \inMi, 2r −1 \inMj}. Then {Nij | i, j} is a partition of {1, 2, . . ., n} into k2 subsets. For n \geqk3 + 1 one of these subsets contains at least k + 1 elements, and the statement follows. Remark. The statement is not necessarily true when n = k3.