IMO 1987 SL 18

Origin: ROM

Problem

For any integer r \geq1, determine the smallest integer h(r) \geq1 such that for any partition of the set {1, 2, . . ., h(r)} into r classes, there are integers a \geq0, 1 \leqx \leqy, such that a + x, a + y, a + x + y belong to the same class.

Solution

Note first that the statement that some a + x, a + y, a + x + y belong to a class C is equivalent to the following statement: (1) There are positive integers p, q \inC such that p < q \leq2p. Indeed, given p, q, take simply x = y = q −p, a = 2p −q; conversely, if a, x, y (x \leqy) exist such that a + x, a + y, a + x + y \inC, take p = a + y, q = a + x + y: clearly, p < q \leq2p. We will show that h(r) = 2r. Let {1, 2, . . ., 2r} = C1 \cupC2 \cup\cdot \cdot \cdot \cupCr be an arbitrary partition into r classes. By the pigeonhole principle, two among the r + 1 numbers r, r + 1, . . . , 2r belong to the same class, say i, j \inCk. If w.l.o.g. i < j, then obviously i < j \leq2i, and so by (1) this Ck has the required property. On the other hand, we consider the partition {1, 2, . . ., 2r −t} = r−t k=1 {k, k + r} \cup{r −t + 1} \cup\cdot \cdot \cdot \cup{r} and prove that (1), and thus also the required property, does not hold. In fact, none of the classes in the partition contains p and q with p < q \leq2p, because k + r > 2k.