Proof of 3-chain subsequence problem from assignment 2 of MIT OCW 6.042 I was trying to solve this question but stuck with how do I prove it so. I do have the intuition but how to prove it? Here is the link to the page and this one is the problem 1!!
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/assignments/MIT6_042JF10_assn02.pdf
Don't tell all the answers but rather give a definitive hint or strategy for the first part!!
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 a1, a2, a3, a4, a5. Note that a monotonically increasing sequences 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.
(a) [4 pts] Assume that a1 < a2. Show that if there is no 3-chain in our sequence, then a3
must be less than a1. (Hint: consider a4!)
(b) [2 pts] Using the previous part, show that if a1 < a2 and there is no 3-chain in our
sequence, then a3 < a4 < a2.
(c) [2 pts] Assuming that a1 < a2 and a3 < a4 < a2, show that any value of a5 must result
in a 3-chain.
(d) [4 pts] Using the previous parts, prove by contradiction that any sequence of five distinct
integers must contain a 3-chain.
 A: Non Contradictory proof - 
A general proof goes like the way, that there are 5 nos, 
a1 _ a2 _ a3 _ a4 _ a5. 
Now, since  there are only 2 symbols available, '<' and '>', there will be repetitions of symbols. And since the question demands that the sequence should not be changed, so there will always be a 3 chain. For all possible combinations, with minimum occurrence of each symbol = 2, a 3 chain sequence can be formed by deleting. For eg.-

1. a1 < a2 > a3 < a4 > a5 | Chain - a1 < a2 < a4 or a2 > a4 > a5
2. a1 > a2 < a3 > a4 < a5 | Chain - a1 > a3 > a4 or a2 < a4 < a5


Answering the question in the form they asked - 
Part 1 -
Now we assume a1 < a2.

So, the 5 numbers would be - a1 < a2 _ a3 _ a4 _ a5.
Proof by contradiction - 
For propositon, lets assume, there is no 3-chain, but a3 > a1. There arise 2 possibilities, which are - 

1 - a1 < a2 < a3
2 - a1 < a3 < a2

The first case cannot be taken(It forms the 3 chain)! In the second case, when we introduce a4, there are 4 possibilities,as - 

1 - a4 < a1 < a3 < a2
2 - a1 < a4 < a3 < a2
3 - a1 < a3 < a4 < a2
4 - a1 < a3 < a2 < a4

As we can see, all of them have a chain, (4,3,2),(4,3,2),(1,3,4),(1,2,4).
Thus, our assumption that a3 > a1, gave no possible combinations.
 Thus our assumption was wrong!!

Part 2 - 
Proof by contradiction - 
From part 1, we know that a3 < a1, the possible combinations that can be made from the three numbers are - 
1 - a3 < a1 < a2

We are given the equation, a3 < a4 < a2, then the proposition will be, a4 < a3 or a4 > a2. This is just converse of the given statement.
Adding a4 to the equation, we get combinations as- 
1 - a4 < a3 < a1 < a2
2 - a3 < a1 < a2 < a4
As we can see, both the combinations give a 3-chain combinations as (4,3,2),(1,2,4).
Thus the assumption that a4 < a3 or a4 > a2 is false, because it is given that there is no 3 - chain to be formed!
Part 3 - 
Proof by contradiction - 
From previous part, and the assumptions in this part, we know that the combinations can be - 

1 - a3 < a4 < a1 < a2
2 - a3 < a1 < a4 < a2

The proposition for the proof can be that, adding a5 doesn't makes any 3 chain.
Adding a5 to the equation, the possible positions can be - 
1 - a5 < a3 < a4 < a1 < a2
2 - a3 < a5 < a4 < a1 < a2
3 - a3 < a4 < a5 < a1 < a2
4 - a3 < a4 < a1 < a5 < a2
5 - a3 < a4 < a1 < a2 < a5

Every possible combination has a 3 - chain. (5,3,1),(5,4,2),(3,4,5),(3,4,5),(1,2,5).
Thus the assumption for a5 can be added to the equation, is wrong!!

In similar manner, the fourth part can be proved!!
A: The first part already contains a good hint. A little more explicit: Suppose the desired conclusion is false, i.e., $a1<a2$ and there is no $3$-chain, but $a3>a1$. How could you choose $a4$ without introducing a $3$-chain?
A: Klaus Draeger has helped you with the first part, and the other parts are similar. Just try to envisage the possible cases at each step of the game – there is no "strategy" involved in this solution approach.
Here is a proof involving less chasing of cases: 
Let ${\bf s}=(s_1,s_2,s_3,s_4)$ be given by
$$s_k:={\rm sgn}(a_{k+1}-a_k)\quad\in\{-1,1\}\ .$$
If ${\bf s}$ contains  two successive  entries of the same sign we are done. It remains to consider the case ${\bf s}=(1,-1,1,-1)$, since symmetry will then take care of $-{\bf s}$. When $a_4> a_2$ then $(a_1, a_2, a_4)$ is an ascending chain, and when $a_4< a_2$ then $(a_2,a_4, a_5)$ is a descending chain, since $s_4=-1$ says that $a_5<a_4$.
