Problem

Source: All-Russian 2022 9.5

Tags: combinatorics



Given an infinite sequence of numbers $a_1, a_2,...$, in which there are no two equal members. Segment $a_i, a_{i+1}, ..., a_{i+m-1}$ of this sequence is called a monotone segment of length $m$, if $a_i < a_{i+1} <...<a_{i+m-1}$ or $a_i > a_{i+1} >... > a_{i+m-1}$. It turned out that for each natural $k$ the term $a_k$ is contained in some monotonic segment of length $k + 1$. Prove that there exists a natural $N$ such that the sequence $a_N , a_{N+1} ,...$ monotonic.