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.
Best Answer
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!!