Problem
ALG-B2-M01-P021 Long monotone segments
An infinite sequence of pairwise distinct real numbers \(a_1,a_2,\ldots\) has the following property: for each \(k\), the term \(a_k\) belongs to some consecutive monotone segment of length \(k+1\). Prove that from some point on, the whole sequence is monotone.
Hint 1. Call an index bad if the direction changes there.
Hint 2. A long monotone segment cannot contain the three terms around a bad index.
Call \(i\ge2\) bad if \(a_{i-1} Assume there are infinitely many bad indices, and choose one bad index \(k\). Take any \(n>k\). By the condition, \(a_n\) belongs to a monotone segment of length \(n+1\). Such a segment cannot contain all three terms \(a_{k-1},a_k,a_{k+1}\), because the direction changes there. Since the segment is so long and contains \(a_n\), it cannot start early enough to include \(a_{k-1}\); hence it must contain \(a_n,a_{n+1},a_{n+2}\). Thus \(n+1\) is not bad. Therefore for every \(n>k\), the index \(n+1\) is not bad, contradicting infinitely many bad indices. Hence there are only finitely many bad indices, and the tail is monotone.
A. Source analysis. Main objects: inequalities, order, an extremal element, or an invariant. The obvious first move usually gives only a local estimate. The hidden observation is to choose the right nondecreasing quantity, or to add/multiply inequalities only after signs are controlled. The needed step is an ordering, an invariant, a product transformation, or a boundary case.
F. Difficulty justification. Final level 8: monotonicity must be replaced by an analysis of bad indices.
G. Why this is not a one-step exercise. One cannot simply choose the longest segment; one must prove that bad indices disappear.