# Proving that there exists no subsequence of 3 numbers that is not monotonically increasing or decreasing in a sequence of 5 distinct numbers

I've been studying discrete math on MIT OCW and came across this problem.

Define a 3-chain to be a (not necessarily contiguous) subsequence of three integers, which is either monotonically increasing or monotonically decreasing. We will show here that any sequence of five distinct integers will contain a 3-chain. Write the sequence as $$a_1, a_2, a_3, a_4, a_5$$. Note that a monotonically increasing sequence is one in which each term is greater than or equal to the previous term. Similarly, a monotonically decreasing sequence is one in which each term is less than or equal to the previous term. Lastly, a subsequence is a sequence derived from the original sequence by deleting some elements without changing the location of the remaining elements.

This problem has multiple parts, each guiding the way to a final solution. I will share my progress and then explain where I'm lost.

(a) Assume that $$a_1 < a_2$$. Show that if there is no 3-chain in our sequence, then $$a_3$$ must be less than $$a_1$$.

My answer: Suppose $$a_3>a_1$$. If $$a_3>a_2,$$ $$\ a_1 is a 3-chain. If $$a_3 and $$a_4, then $$a_2>a_3>a_4$$ is a 3-chain. If $$a_4>a_3$$, then $$a_1 is a 3-chain. Thus $$a_3$$ must be less than $$a_1$$.

(b) Using the previous part, show that if $$a_1 and there is no 3-chain in our sequence, then $$a_3.

My answer: If $$a_3>a_4$$, then $$a_1>a_3>a_4$$ is a 3-chain. Thus $$a_4>a_3$$. If $$a_4>a_2$$, then $$a_1 is a 3-chain. Thus $$a_3.

(c) Assuming that $$a_1 and $$a_3, show that any value of $$a_5$$ must result in a 3-chain.

My answer: If $$a_5>a_4$$, then $$a_3 is a 3-chain. If $$a_5, then $$a_3 is a 3-chain. Thus, any value of $$a_5$$ results in a 3-chain.

(d) Using the previous parts, prove by contradiction that any sequence of 5 distinct integers must contain a 3-chain.

This is where I got lost. Doesn't all this just prove that $$a_1>a_2$$ since we initially assumed that $$a_1?

• If $a_1<a_2$, consider the sequence $-a_1,-a_2,-a_3,-a_4,-a_5$, and note that it has a $3$-chain if and only the original sequence has one (of the opposite type). Apr 28, 2020 at 19:40
• Your title does not accurately reflect the statement you want to prove. Apr 28, 2020 at 20:01

The assumption for the contradiction is that there exists a sequence of 5 distinct integers $$a_1,\cdots,a_5$$ which do not contain a 3-chain.
There are two possibilities since $$a_i$$ are assumed to be distinct, either $$a_1 or $$a_1>a_2$$. If $$a_1, then by the symmetry of the arguments, we still have the same result with a reversal of direction but still monotone. As @BrianM.Scott has pointed out, we can apply an identical argument to $$-a_1,\cdots,-a_5$$ which is monotone if and only if the original sequence is monotone.
So assume WLOG that $$a_1. Then our assumption that there is no 3-chain (and WLOG that $$a<1) allow us to use part a to justify using part b and then using part b to justify using part c, as you have proven. Thus our assumption gives that for any possible value of $$a_5$$, ie in all cases, we have a 3-chain. So the assumption that there IS a 3-chain implies that there NOT a 3-chain. This is a contradiction. Since we could have chosen $$a_1>a_2$$ and reached the same contradiction, then we always have a contradiction for any sequence of 5 distinct integers, thus the original assumption that there is not a 3-chain is false.