MathDB

M2703

Part of Kvant 2022

Problems(1)

Monotonic blocks in a sequence

Source: All-Russian 2022 9.5

4/20/2022
Given an infinite sequence of numbers a1,a2,...a_1, a_2,..., in which there are no two equal members. Segment ai,ai+1,...,ai+m−1a_i, a_{i+1}, ..., a_{i+m-1} of this sequence is called a monotone segment of length mm, if ai<ai+1<...<ai+m−1a_i < a_{i+1} <...<a_{i+m-1} or ai>ai+1>...>ai+m−1a_i > a_{i+1} >... > a_{i+m-1}. It turned out that for each natural kk the term aka_k is contained in some monotonic segment of length k+1k + 1. Prove that there exists a natural NN such that the sequence aN,aN+1,...a_N , a_{N+1} ,... monotonic.
combinatorics