Proof of 3-chain subsequence problem from assignment 2 of MIT OCW 6.042

Question

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.

Answer 1

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?

Answer 2

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

Answer 3

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