0
$\begingroup$

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 ${a}_{1},{a}_{2},{a}_{3},{a}_{4},{a}_{5}$. 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) Assume that $a1 < a2$. Show that if there is no $3$-chain in our sequence, then $a_3$ must be less than $a_1$. (Hint: consider $a_4$!)

(b) Using the previous part, show that if $a_1 < a_2$ and there is no $3$-chain in our sequence, then $a_3 < a_4 < a_2$.

(c) Assuming that $a_1 < a_2$ and $a_3 < a_4 < a_2$, show that any value of $a_5$ must result in a $3$-chain.

(d) Using the previous parts, prove by contradiction that any sequence of five distinct integers must contain a $3$-chain.

Source: MIT OCW Mathematics for Computer Science, Problem Set 2, Problem 1.

What I have done:

Part (a):

Theorem: if there is no 3-chain in our sequence, then $a_3$ must be less than $a_1$

Proof: We use proof by contradiction

1) Let's assume that there is no 3-chain sequence and $a_3 \ge a_1$

2) This gives rise to two possible cases:

Case 1: $a_1<a_2<a_3 $

Case 2: $a_1<a_3<a_2$

3) Case 1: this case will always form a 3-chain no matter where we introduce $a_4$. Therefore, we can disregard this case without deeper case analysis.

4) Case 2: let's consider the two sub-cases in which we introduce $a_4$:

Sub-case 1: $a_4\lt a_3$

Sub-case 2: $a_3\lt a_4$

  1. $a_4<a_1<a_3<a_2$

  2. $a_1<a_3<a_2<a_4$

We can see that both of these cases give a 3-chain:

$a_4<a_3<a_2$

$a_1<a_3<a_4$

so our second case can be disregarded.

5) So, our original assumption, there is no 3-chain sequence and $a_3\ge a_1$, was wrong. This leads us to a contradiction.

Q.E.D.

Part (b):

Theorem: If $a_1<a_2$, and there is no 3-chain in our sequence, then $a_3<a_4<a_2$

Proof: We use proof by contradiction.

1) Assume that $a_1<a_2$ and there is no 3-chain in our sequence and $a_3\ge a_4\ge a_2$

2) We know, from the previous part, that $a_3<a_1<a_2$

3) By introducing $a_4$ and by using the conditions $a_4\le a_3$ and $a_2\le a_4$, we get two cases:

  1. $a_3<a_1<a_2<a_4$

  2. $a_4<a_3<a_1<a_2$

4) Both of these cases give $3$-chains. Thus, our original assumption was wrong since we have reached a contradiction.

Q.E.D.

Part (c):

Proof: this proof is by case analysis.

1) Since we are given that $a_1<a_2$ and $a_3<a_4<a_2$ we can have the following cases:

Case 1: $a_1<a_3<a_4<a_2$

Case 2: $a_3<a_1<a_4<a_2$

Case 3: $a_3<a_4<a_1<a_2$

2) Now, we can see that we will have a 3-chain no matter where we introduce $a_5$ in Case 1. So, we can disregard Case 1 right away.

3) We can now perform a deeper analysis on Case 2 and Case 3 by creating subcases for each case. Each subcase will introduce $a_5$ in a unique position in the original case.

Case 2:

Subcase 1. $a_5<a_3<a_1<a_4<a_2$

Subcase 2. $a_3<a_5<a_1<a_4<a_2$

Subcase 3. $a_3<a_1<a_5<a_4<a_2$

Subcase 4. $a_3<a_1<a_4<a_5<a_2$

Subcase 5. $a_3<a_1<a_4<a_2<a_5$

Case 3:

Subcase 1. $a_5<a_3<a_4<a_1<a_2$

Subcase 2. $a_3<a_5<a_4<a_1<a_2$

Subcase 3. $a_3<a_4<a_5<a_1<a_2$

Subcase 4. $a_3<a_4<a_1<a_5<a_2$

Subcase 5. $a_3<a_4<a_1<a_2<a_5$

We can see that the subcases of Case 1 and Case 2 all have $3$-chains.

4) Therefore, any value of $a_5$ will result in a $3$-chain

Q.E.D.

Part (d):

Theorem: any sequence of five distinct integers must contain a $3$-chain.

Proof: by contradiction.

1) From part (a), given that $a_1 < a_2$, we know that there msut be a $3$0chain in our sequence.

2) By the symmetry of $<$ and $>$, the argument found in step 1), could be applied in the case of $a_1 > a_2$.

3) By combining part (b) and part (c), we get that:

no $3$-chain implies $a_3 < a_4 < a_2$ which implies a $3$-chain. This is a contradiction. Thus, there must be a $3$-chain. (Given that $a_1 < a_2$).

4) By the symmetry between $<$ and $>$,this same argument could be applied in the case of $a_1 > a_2$.

5) Therefore, any sequence of give distinct integers must contain a $3$-chain.

Q.E.D.

I have written up the proofs for the sub problems to the best of my ability. I would like to have them reviewed. I would appreciate any and all help with identifying the errors, and with helping me improve the proof(s).

$\endgroup$
  • $\begingroup$ So much text, and not a single question mark! What's your question? $\endgroup$ – joriki Jun 25 '16 at 15:58
  • $\begingroup$ @joriki I am asking for someone to review my proof(s). Edit: I have added the reason I have posted this and what I would like help with. $\endgroup$ – Cherry_Developer Jun 25 '16 at 16:00
3
$\begingroup$

You may go through all the possible sub-cases, but that is quite painful.

By Dilworth's theorem or the Erdos-Szekeres theorem, any sequence with length $n^2+1$ contains a monotonic subsequence of length $n+1$. Have a look at the simple proof through the Pigeonhole principle.

$\endgroup$

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.