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.