IMC 2004 · Day 1 · P5

We prove a more general statement:

Lemma. Let $k, l \ge 2$, let $X$ be a set of $\binom{k+l-4}{k-2} + 1$ real numbers. Then either $X$ contains an increasing sequence $\{x_i\}_{i=1}^{k} \subseteq X$ of length $k$ and $$|x_{i+1} - x_1| \ge 2 |x_i - x_1| \quad \forall i = 2, \dots, k-1,$$ or $X$ contains a decreasing sequence $\{x_i\}_{i=1}^{l} \subseteq X$ of length $l$ and $$|x_{i+1} - x_1| \ge 2 |x_i - x_1| \quad \forall i = 2, \dots, l-1.$$

Proof of the lemma. We use induction on $k + l$. In case $k = 2$ or $l = 2$ the lemma is obviously true.

Now let us make the induction step. Let $m$ be the minimal element of $X$, $M$ be its maximal element. Let $$X_m = \left\{ x \in X : x \le \frac{m+M}{2} \right\}, \qquad X_M = \left\{ x \in X : x > \frac{m+M}{2} \right\}.$$ Since $\binom{k+l-4}{k-2} = \binom{k+(l-1)-4}{k-2} + \binom{(k-1)+l-4}{(k-1)-2}$, we can see that either $$|X_m| \ge \binom{(k-1)+l-4}{(k-1)-2} + 1, \quad \text{or} \quad |X_M| \ge \binom{k+(l-1)-4}{k-2} + 1.$$ In the first case we apply the inductive assumption to $X_m$ and either obtain a decreasing sequence of length $l$ with the required properties (in this case the inductive step is made), or obtain an increasing sequence $\{x_i\}_{i=1}^{k-1} \subseteq X_m$ of length $k-1$. Then we note that the sequence $\{x_1, x_2, \dots, x_{k-1}, M\} \subseteq X$ has length $k$ and all the required properties.

In the case $|X_M| \ge \binom{k+(l-1)-4}{k-2} + 1$ the inductive step is made in a similar way. Thus the lemma is proved.

The reader may check that the number $\binom{k+l-4}{k-2} + 1$ cannot be smaller in the lemma.