IMC 2004, Day 1, Problem 5
Let be a set of real numbers, . Prove that there exists a monotone sequence such that
for all .
Original from the official PDF
![Let X be a set of 2k−4 k−2 + 1 real numbers, k ≥ 2. Prove that there exists a monotone sequence {x i } ki=1 ⊆ X such that |x i+1 − x | ≥ 2|x i − x | for all i = 2, . . . , k − 1. [20 points]](/archive/imc/imc-2004-d1-p5.png)
This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Solution. We prove a more general statement:
Lemma. Let , let be a set of real numbers. Then either contains an increasing sequence of length and
Proof of the lemma. We use induction on . In case or the lemma is obviously true.
Now let us make the induction step. Let be the minimal element of , be its maximal element. Let
In the first case we apply the inductive assumption to and either obtain a decreasing sequence of length with the required properties (in this case the inductive step is made), or obtain an increasing sequence of length . Then we note that the sequence has length and all the required properties.
In the case the inductive step is made in a similar way. Thus the lemma is proved.
The reader may check that the number cannot be smaller in the lemma.
Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.