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$
$a_4<a_1<a_3<a_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:
$a_3<a_1<a_2<a_4$
$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).
