IMO 1990 SL 4

Origin: CZS

Problem

Assume that the set of all positive integers is decomposed into r (disjoint) subsets A1 \cupA2 \cup\cdot \cdot \cdot Ar = N. Prove that one of them, say Ai, has the following property: There exists a positive m such that for any k one can find numbers a1, a2, . . . , ak in Ai with 0 < aj+1 −aj \leqm (1 \leqj \leqk −1).

Solution

Assuming that A1 is not such a set Ai, it follows that for every m there exist m consecutive numbers not in A1. It follows that A2 \cupA3 \cup\cdot \cdot \cdot \cupAr contains arbitrarily long sequences of numbers. Inductively, let us assume that Aj \cupAj+1 \cup\cdot \cdot \cdot\cupAr contains arbitrarily long sequences of consecutive numbers and none of A1, A2, . . . , Aj−1 is the desired set Ai. Let us assume that Aj is also not Ai. Hence for each m there exists k(m) such that among k(m) elements of Aj there exist two consecutive elements that differ by at least m. Let us consider m\cdotk(m) consecutive numbers in Aj\cup\cdot \cdot \cdot\cupAr, which exist by the induction hypothesis. Then either Aj contains fewer than k(m) of these integers, in which case Aj+1\cup\cdot \cdot \cdot\cupAr contains m consecutive integers by the pigeonhole principle or Aj contains k(m) integers among which there exists a gap of length m of consecutive integers that belong to Aj+1 \cup\cdot \cdot \cdot \cupAr. Hence we have proven that Aj+1 \cup\cdot \cdot \cdot \cupAr contains sequences of integers of arbitrary length. By induction, assuming that A1, A2, . . . , Ar−1 do not satisfy the conditions to be the set Ai, it follows that Ar contains sequences of consecutive integers of arbitrary length and hence satisfies the conditions necessary for it to be the set Ai.