5
$\begingroup$

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.

$\endgroup$

3 Answers 3

6
$\begingroup$

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

$\endgroup$
0
4
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 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!! $\endgroup$ Nov 6, 2014 at 15:00
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 6, 2014 at 15:05
  • $\begingroup$ 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!! $\endgroup$ Nov 6, 2014 at 15:55
  • 2
    $\begingroup$ 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?) $\endgroup$ Nov 6, 2014 at 17:09
  • 2
    $\begingroup$ 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$. $\endgroup$ Nov 6, 2014 at 17:12
3
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ You can actually simplify this even more, since the problem specifies distinct integers, i.e. $s_k$ cannot be $0$. $\endgroup$ Nov 6, 2014 at 15:27
  • $\begingroup$ @Klaus Draeger: Thank you. It seems that I was confused by the complicated explanation of monotonicity. $\endgroup$ Nov 6, 2014 at 15:39
  • $\begingroup$ @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!! $\endgroup$ Nov 6, 2014 at 16:06
  • $\begingroup$ @dex: The problem as stated involves "five distinct integers". $\endgroup$ Nov 6, 2014 at 16:16
  • $\begingroup$ 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. $\endgroup$ Nov 6, 2014 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.