6
$\begingroup$

This task is from MIT OpenCourse Mathematics for CS 2010 course, problem set 2, exercise 1(d). I am aware that this question has already been asked several times previously on this platform. Yet, the replies that were given did not help me with my particular question.

Problem statement:

Given: A sequence of five distinct integers $(a_1, ..., a_5)$.
Show: Prove by contradiction, that any such sequence contains a 3-chain

(Define a 3-chain to be a (not necessarily contiguous) subsequence of three integers,
which is either monotonically increasing or monotonically decreasing).

For the prove you are allowed to use the following findings from (a)-(b):
$$\nexists3{\text -}chain \wedge (a_1<a_2) \implies (a_1<a_3)$$ $$\nexists3{\text -}chain \wedge (a_1<a_2) \implies (a_3<a_4<a_2)$$ $$ (a_1<a_2) \wedge (a_3<a_4<a_2) \implies \exists3{\text -}chain$$

Proof: Assume $\nexists3{\text -}chain$. Then from (a) and (b) we know: $(a_1<a_2) \implies ((a_1<a_3) \wedge (a_3<a_4<a_2))$, and we have a $3{\text -}chain$ $a_1<a_3<a_4$. Contradiction! (*)

Problem: this contradiction relies on the assumption $a_1<a_2$. How can we get rid of this condition?

Update: In case $a_1>a_2$, multiply the sequence $(a_1, ..., a_5)$ with -1. We get a sequence $(-a_1, ..., -a_5)$ with $-a_1<-a_2$. From (*) follows that $(-a_1, ..., -a_5)$ contains a 3-chain. Then, by the symmetry, $(a_1, ..., a5)$ also contains a 3-chain. $\blacksquare$

Before update:

One idea I was given is to use symmetry: f.e., if $(a_1, ..., a_5)$ with $a_1<a_2$ has a $3{\text-}chain$, then a sequence $(-a_1, ..., > -a_5)$ would have $a_1>a_2$ and would also contain a $3{\text-}chain$ just with the reversed monotony. Though I see why this true, I am not sure if this argument is right for this problem. What about $(a_1, > ..., a_5)$ exactly the same as for the case $a_1<a_2$ where we just switch $a_1, a_2$ and get $a_1>a_2$, i.e., we do not reverse the signs of the elements?

Question 1: How would you write the prove using given information? (Not referring to theorems for general case).
Question 2: If you think the argument with the symmetry is the right way to go, could you please write how you would phrase it and maybe fill some logical steps I am missing in order to make it robust?

$\endgroup$
1

3 Answers 3

6
$\begingroup$

Let the numbers be $A,B,C,D,E$

Let Solid line indicate $X<Y$ , while Dashed line indicate $X>Y$ , in this Solution with graphs.
When 2 Points have no line , it means we are not yet sure which condition holds.

CORE IDEA : When we have 2 Consecutive Solid lines , we have $X<Y<Z$ which is a 3-Chain ; When we have 2 Consecutive Dashed lines , we have $X>Y>Z$ which is a 3-Chain

We then have to check what occurs when we have alternating Solid lines & Dashed lines like this :

ABCDE 1

Here we assume the 5 Points are the $5$ numbers in order & we are considering the Case $A<B$

In Case , $A<C$ , we get this graph & the 3-Chain is $ACD$

ABCDE 2

Else , we have this graph , where $A>D$ is also shown :

ABCDE 3

Then the 3-Chain is $ADE$

We might get unlucky & $A<D$ , which looks like this :

ABCDE 4

We are almost DONE with the Proof !
Check $B$ & $D$ , Either $B<D$ or $B>D$ , giving these 2 graphs :

ABCDE 5

ABCDE 6

We will get 2 Solid lines to get the 3-Chain $ABD$ or we will get 2 Dashed lines to get the 3-Chain $BDE$

DONE !

When we consider the Case when $A>B$ , Proof Outline will Symmetrically match.

$\endgroup$
1
  • 1
    $\begingroup$ That looks fancy. Thank you for the solution, I will try to understand it. I doubt the MIT professor meant the problem to be solved with graphs as they are taught later in the course. $\endgroup$
    – Lina
    Commented Jun 24 at 16:43
2
$\begingroup$

Your symmetry argument is basically correct. The reason is that your assumptions can be reduced to just a totally ordered set with 5 elements. If you prove that your three findings are valid for a total order $<$ then they are also valid for $\gt.$ Taking the dual order is equivalent to changing signs in this case..

Another argument goes:

Take the first element $a_1$. Then among the middle elements $a_2, a_3, a_4$ there are 2 that are either both greater or both smaller than $a_1$. Similarly there are 2 middle elements that are either both greater or both smaller than $a_5.$ So take $a_i$ to be in the intersection of both sets. If $a_1 < a_i < a_5$ or vice versa then you are done.

Otherwise $a_1 < a_i \gt a_5$ or something symmetrical. Then one of the remaining numbers $a_j$ is greater than $a_1$ and $a_5$. (Just take the maximum of the 2 remaining elements.) Then $a_i$ and $a_j$ form a $3$-chain together with one of $a_1$ or $a_5$.

$\endgroup$
3
  • $\begingroup$ Both @Prem's solution and mine further show that the chain contains the first or last element. This is because we are not making heavy use of contradiction by assuming that no such chain exists. $\endgroup$
    – Keplerto
    Commented Jun 24 at 18:38
  • $\begingroup$ Interesting. Thank you. Also I updated my proof with symmetry. $\endgroup$
    – Lina
    Commented Jun 24 at 18:51
  • $\begingroup$ Yeah, I think it's fine now $\endgroup$
    – Keplerto
    Commented Jun 24 at 18:54
0
$\begingroup$

I'd use the trichotomy property: Given any two real numbers $x$ and $y$, either $x=y, x<y, x>y$. We are given that the 5 integers are distinct, so no integers are equal to each other.

That means for any pair from the five, $a,b$, we have $a<b$. Now for some third number $c$, $c<a$ or $c>a$ and $c<b$ or $c>b$. If $c<a$ or $c>b$, then we have a 3-cycle. Note these scenarios cancel each other out, if $c>b$ then $\lnot (c<a)$ and vice versa.

Suppose $c>a$. We've already established a 3-cycle if $c>b$, so let's also assume $c<b$. Then $a<c<b$, so we have a 3 cycle.

All possible scenarios have been addressed and in each case, we have a 3 cycle.

$\endgroup$
9
  • $\begingroup$ Thank you for the reply. That is a good idea. I am going through all possible cases. I am afraid the case you pointed out with a<b and c<a does not qualify, as 3-chain is defined as a monotonic subsequence of (a, b, c, d, e). So in that case we need to consider d, I guess. Lots of cases. $\endgroup$
    – Lina
    Commented Jun 24 at 15:15
  • $\begingroup$ a 3 chain is a monotonic 3 member subset of any elements, right? I could be misunderstanding the definition. So if c<a and a<b, then c <a < b by transitivity and we have a 3 chain. $\endgroup$ Commented Jun 24 at 15:23
  • $\begingroup$ "Define a 3-chain to be a (not necessarily contiguous) subsequence of three integers, which is either monotonically increasing or monotonically decreasing)". F.e., in (1, 3, 0, 5, 8) would be (1, 3, 5) or (3, 5, 8). I do not think we can treat sequences as sets. $\endgroup$
    – Lina
    Commented Jun 24 at 15:26
  • 2
    $\begingroup$ @Prem, we are currently discussing it in the comments to the answer. $\endgroup$
    – Lina
    Commented Jun 24 at 16:12
  • 1
    $\begingroup$ Prem, I think you are right. At the very least something has to be added to my proof. $\endgroup$ Commented Jun 24 at 16:18

You must log in to answer this question.

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