Finding order when disordering an ordered set

Question

Let $S=\{a_1,a_2,\dots, a_m\}$ be some ordered set, such that $a_i<a_{i+1}$.

I find that, no matter how much I try, I can not totally disorder the set without finding some subset of the resulting disordered set where order is still preserved among its elements, which form a monotonically increasing or decreasing sequence.

After some experimentation, it seems that a set of $2^{n-1}$ elements guarantees at least some monotonically increasing or decreasing sequence of $n$ elements for any disordered set I make, with only one exception for $n=3$: $\{a_2,a_1,a_4,a_3\}$ It can be seen that no subset of $3$ elements can be chosen from this disordered set that form a monotonically increasing or decreasing sequence. However, this is the only one I have found.

I am not sure if this guess is correct, and no clue about how to prove or disprove it; any correction, counterexample, or reference about this would be really welcomed.

Thanks!

Answer 1

By (a special case of) the Erdos-Szekeres theorem, any sequence of $(n-1)^2+1$ numbers contains an increasing or decreasing sequence of $n$ numbers.

Since $2^{n-1}\ge(n-1)^2+1$ for $n\ge6$, this proves your conjecture for these values of $n$. It remains to check $n=4$ and $n=5$. Counterexamples in these cases follow a simple pattern:

• $6,7,8;\quad 3,4,5;\quad 1,2$;
• $13,14,15,16;\quad 9,10,11,12;\quad 5,6,7,8;\quad 1,2,3,4$.

The semicolons and large spaces emphasize the structure. In the first example, any four numbers must include two from the same group, so cannot be decreasing; and must include two from different groups, so cannot be increasing. Same goes for five numbers in the second example.