Prove that for $n\in\mathbb{Z}^+$, a sequence of $n^3$ elements either has $n$ equal elements or a monotone subsequence with $n$ elements.

Question

Prove that $\forall n\in\mathbb{Z}^+$, a sequence with $n^3$ elements either has $n$ equal elements or a monotone subsequence with $n$ elements (strictly increasing or strictly decreasing).

I tried to apply the pigeonhole principle but had no idea how to go on. Anyone can give me a hint?

score 2 · Accepted Answer · answered Sep 18 '18 at 17:08

2

Without $n$ equal element, each element occurs at most $n-1$ occurrences and so there are at least $n^3/(n-1)>n^2+n+1$ distinct elements. Deleting repetitions gives a sequence of at least $n^2+n+1$ distinct elements. Now apply Erdos-Szekeres.

answered Sep 18 '18 at 17:08

Angina Seng

158,341

Prove that for $n\in\mathbb{Z}^+$, a sequence of $n^3$ elements either has $n$ equal elements or a monotone subsequence with $n$ elements.

1 Answers1