# 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.

#### Solutions Collecting From Web of "Proof of 3-chain subsequence problem from assignment 2 of MIT OCW 6.042"

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 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

Part 1
Now we assume a1 < a2.

So, the 5 numbers would be – a1 < a2 _ a3 _ a4 _ a5.
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 –
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 –
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!!

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$.