Jump to content


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 :-)
Guest Message by DevFuse
 

Photo
- - - - -

Infinite monotone subsequence


  • Please log in to reply
22 replies to this topic

#1 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 07 September 2012 - 10:19 PM

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).
  • 0

#2 jim

jim

    Junior Member

  • Members
  • PipPip
  • 33 posts

Posted 07 September 2012 - 11:25 PM

You need to change to the standard definition of montone. Monotone increasing means each number is at least as large as the previous number. If each successive number is actually larger that is called strictly monotone. Decreasing monotone is defined in a similar way. Note 1,1,1,1,1,1,1,... would need my definition to have any montone sequence of length greater than one.
  • 0

#3 Rob_Gandy

Rob_Gandy

    Advanced Member

  • Members
  • PipPipPip
  • 175 posts
  • Gender:Male
  • Location:Garland, TX

Posted 07 September 2012 - 11:32 PM

I was thinking along the same lines as jim. Using your definitions you cannot create an infinite monotone subsequence from a sequence of one repeated number.
  • 0

#4 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

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
Spoiler for

  • 0

#5 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 08 September 2012 - 03:54 PM

I defined a sequence as a set, which means no two numbers can be equal. And a proof for each finite sequence is not quite enough to prove the infinite extension. For example, every finite sequence has a largest number but this doesn't imply that an infinite sequence has a largest number.
  • 0

#6 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 08 September 2012 - 04:10 PM

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

#7 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

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,
Spoiler for Proof by contradiction

  • 0

#8 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 09 September 2012 - 03:01 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.
  • 0

#9 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5575 posts
  • Gender:Male
  • Location:New York

Posted 09 September 2012 - 06:05 AM

Spoiler for assume


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

Does OP distinguish between countably and uncountably infinite?

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#10 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

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
Spoiler for

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users