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

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

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?

• I think then I am confused about the 3-chain part only!! What I have understood about it from the question is that following are the possible combinations for the 3-chain -- a1-a2-a3, a1-a2-a4, a1-a3-a4, a2-a3-a4, a1-a2-a5, a1-a3-a5, a2-a3-a5, a1-a4-a5, a2-a4-a5, a3-a4-a5. I think I am somewhere wrong with the concept only after reading your answer. Please help me figure out that!! Nov 6, 2014 at 15:00
• Those are the possible triples making up a $3$-chain, yes. For each of these there are two possible chains, i.e. for $a1-a2-a4$ you could have $a1<a2<a4$ or $a1>a2>a4$. In this question, you want to avoid all those possibilities, and in part 1, we are now assuming that we already have that $a1<a2$ and $a1<a3$. What can we deduce from this and from the absence of chains? Nov 6, 2014 at 15:05
• Got the first part!! So, do you mean to say that the line "there is no 3-chain in our sequence" means that there is no such chain out of all that i mentioned above ^^ let's say of the generic form x-y-z for which both x>y>z and x<y<z are possible( meaning only one of them can exit )? And, I deduced from the assumption $a1<a2$ and $a1<a3$ is that then I don't know the relation between a2 and a3 thus the result becomes undefined!! But, if $a1>a3$ we can definitely say that $a3<a1<a2$ which surely doesnot follow the principles of 3-chain rule. Correct me over that wherever you feel so!! Nov 6, 2014 at 15:55
• Yes, the condition means that none of those chains occur. So we cannot have $a1<a2<a3$, nor $a1>a2>a3$, nor $a1<a2<a4$, nor... Now it is true that $a1<a2$ and $a1<a3$ do not directly tell us how $a2$ and $a3$ are related. We could have $a2<a3$ or $a3<a2$. But note that one of these introduces a $3$-chain, so we must have the other (which?) Nov 6, 2014 at 17:09
• Once we have the relation between $a2$ and $a3$ figured out, the next question is where $a4$ fits in. Suppose for example that we have $a1<a3<a2$, there are in theory four options: $a4$ could be (1) less than $a1$, (2) between $a1$ and $a3$, (3) between $a3$ and $a2$, or (4) greater than $a2$. The question then is again which of these we can choose without introducing a chain; for example (4) is out since it would imply $a1<a2<a4$. Nov 6, 2014 at 17:12

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

• You can actually simplify this even more, since the problem specifies distinct integers, i.e. $s_k$ cannot be $0$. Nov 6, 2014 at 15:27
• @Klaus Draeger: Thank you. It seems that I was confused by the complicated explanation of monotonicity. Nov 6, 2014 at 15:39
• @KlausDraeger Why it would be so that $s_k$ cannot be zero? The question defines monotonic sequences with the inclusion of chances of having a term equal to the previous term for both monotonically increasing as well as decreasing sequence!! Nov 6, 2014 at 16:06
• @dex: The problem as stated involves "five distinct integers". Nov 6, 2014 at 16:16
• I am most probably having all the confusion with the 3-chain thing only. That's why I am to understand this as follows. I understand that when $a_4>a_2$ then $(a_1,a_2,a_4)$ is an ascending chain, but how come this happened that when $a_4<a_2$ then $(a_2,a_4,a_5)$ is a descending chain? This I could not understand, please try to explain this thing because I feel that it would help me to clear all my confusions regarding 3-chain thing. Nov 6, 2014 at 16:19