Problem

Source: 2018 Swedish Mathematical Competition p3

Tags: combinatorics, Sequence



Let m be a positive integer. An $m$-pattern is a sequence of $m$ symbols of strict inequalities. An $m$-pattern is said to be realized by a sequence of $m + 1$ real numbers when the numbers meet each of the inequalities in the given order. (For example, the $5$-pattern $ <, <,>, < ,>$ is realized by the sequence of numbers $1, 4, 7, -3, 1, 0$.) Given $m$, which is the least integer $n$ for which there exists any number sequence $x_1,... , x_n$ such that each $m$-pattern is realized by a subsequence $x_{i_1},... , x_{i_{m + 1}}$ with $1 \le i_1 <... < i_{m + 1} \le n$?