1
$\begingroup$

I've been studying discrete math on MIT OCW and came across this problem.

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

This problem has multiple parts, each guiding the way to a final solution. I will share my progress and then explain where I'm lost.

(a) Assume that $a_1 < a_2$. Show that if there is no 3-chain in our sequence, then $a_3$ must be less than $a_1$.

My answer: Suppose $a_3>a_1$. If $a_3>a_2,$ $\ a_1<a_2<a_3$ is a 3-chain. If $a_3<a_2$ and $a_4<a_3$, then $ a_2>a_3>a_4$ is a 3-chain. If $a_4>a_3$, then $a_1<a_3<a_4$ is a 3-chain. Thus $a_3$ must be less than $a_1$.

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

My answer: If $a_3>a_4$, then $a_1>a_3>a_4$ is a 3-chain. Thus $a_4>a_3$. If $a_4>a_2$, then $a_1<a_2<a_4$ is a 3-chain. Thus $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.

My answer: If $a_5>a_4$, then $a_3<a_4<a_5$ is a 3-chain. If $a_5<a_4$, then $a_3<a_4<a_5$ is a 3-chain. Thus, any value of $a_5$ results in a 3-chain.

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

This is where I got lost. Doesn't all this just prove that $a_1>a_2$ since we initially assumed that $a_1<a_2$?

$\endgroup$
2
  • 1
    $\begingroup$ If $a_1<a_2$, consider the sequence $-a_1,-a_2,-a_3,-a_4,-a_5$, and note that it has a $3$-chain if and only the original sequence has one (of the opposite type). $\endgroup$ Apr 28, 2020 at 19:40
  • $\begingroup$ Your title does not accurately reflect the statement you want to prove. $\endgroup$
    – RobPratt
    Apr 28, 2020 at 20:01

1 Answer 1

1
$\begingroup$

The assumption for the contradiction is that there exists a sequence of 5 distinct integers $a_1,\cdots,a_5$ which do not contain a 3-chain.

There are two possibilities since $a_i$ are assumed to be distinct, either $a_1<a_2$ or $a_1>a_2$. If $a_1<a_2$, then by the symmetry of the arguments, we still have the same result with a reversal of direction but still monotone. As @BrianM.Scott has pointed out, we can apply an identical argument to $-a_1,\cdots,-a_5$ which is monotone if and only if the original sequence is monotone.

So assume WLOG that $a_1<a_2$. Then our assumption that there is no 3-chain (and WLOG that $a<1<a_2$) allow us to use part a to justify using part b and then using part b to justify using part c, as you have proven. Thus our assumption gives that for any possible value of $a_5$, ie in all cases, we have a 3-chain. So the assumption that there IS a 3-chain implies that there NOT a 3-chain. This is a contradiction. Since we could have chosen $a_1>a_2$ and reached the same contradiction, then we always have a contradiction for any sequence of 5 distinct integers, thus the original assumption that there is not a 3-chain is false.

$\endgroup$

You must log in to answer this question.

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