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$
2
  • $\begingroup$ So much text, and not a single question mark! What's your question? $\endgroup$
    – joriki
    Jun 25, 2016 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$ Jun 25, 2016 at 16:00

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .