## Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |

# Infinite monotone subsequence

### #1

Posted 07 September 2012 - 10:19 PM

---

Sequence: a set with a specified order of its elements. For example {1-2-4-3} is a different sequence from {4-1-3-2}.

Subsequence: a subset retaining the order of the original sequence. For example {2-3-5-7} is a subsequence of {1-2-3-4-5-6-7}.

Monotone: either increasing (each number is smaller than the next number) or decreasing (each number is larger than the next number).

### #2

Posted 07 September 2012 - 11:25 PM

### #3

Posted 07 September 2012 - 11:32 PM

### #4

Posted 08 September 2012 - 07:30 AM

Show that every infinite sequence of real numbers contains an infinite monotone subsequence.

---

Sequence: a set with a specified order of its elements. For example {1-2-4-3} is a different sequence from {4-1-3-2}.

Subsequence: a subset retaining the order of the original sequence. For example {2-3-5-7} is a subsequence of {1-2-3-4-5-6-7}.

Monotone: either increasing (each number is smaller than the next number) or decreasing (each number is larger than the next number).

Let's relax the definition of monotone a bit and say that in a increasing monotone sequence, each number is bigger than or equal to than the last number. Same with decreasing monotone sequence. Then the statement in the OP is an extension of a previous puzzle

### #5

Posted 08 September 2012 - 03:54 PM

### #6

Posted 08 September 2012 - 04:10 PM

### #7

Posted 09 September 2012 - 02:34 AM

To be more specific, you have proven that there are arbitrarily long monotone sub-sequences, but not that there are infinitely long ones.

How about this proof then,

### #8

Posted 09 September 2012 - 03:01 AM

Suppose you are standing at a crossroads, with an infinite number of roads leading away from it. Each road is numbered with a unique natural number, and each road is n miles long where n is the number of the road. Whichever of these roads you choose (say road number p), it will eventually end (after p miles), so no road has infinite length. But you could always have chosen another road that is longer (road number p+1 for example).

The same thing could be true for these subsequences. You have proven that there is no longest monotone subsequence, but that doesn't imply that there is an infinite monotone subsequence.

### #9

Posted 09 September 2012 - 06:05 AM

Edit: Ah, you said real, not natural. The crossroads derailed my thinking.

Does OP distinguish between countably and uncountably infinite?

*The greatest challenge to any thinker is stating the problem in a way that will allow a solution.*

- Bertrand Russell

### #10

Posted 09 September 2012 - 06:30 AM

Sorry, but there is an error in that proof. Assumption ~A does not imply that there is a monotone subsequence with maximum finite length M.

Suppose you are standing at a crossroads, with an infinite number of roads leading away from it. Each road is numbered with a unique natural number, and each road is n miles long where n is the number of the road. Whichever of these roads you choose (say road number p), it will eventually end (after p miles), so no road has infinite length. But you could always have chosen another road that is longer (road number p+1 for example).

The same thing could be true for these subsequences.You have proven that there is no longest monotone subsequence, but that doesn't imply that there is an infinite monotone subsequence.

Let me restate the proof in a more direct way, and we'll see if we get anywhere

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users