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


  • Please log in to reply
6 replies to this topic

#1 bushindo

bushindo

    Senior Member

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

Posted 02 January 2010 - 03:47 AM

I saw this problem in a test long ago.

Assume that we have a sequence of 17 distinct integers. Show that there exist at least 1 subsequence of 5 integers that form an increasing or decreasing sequence.

For instance, let the sequence of 17 distinct integers be
9, 13,  6,  1, 11,  7, 16,  3, 15, 10,  2,  5, 12,  4, 14,  8, 17

Then there is a increasing subsequence of length 5 in (1,3,5,8,17). There is also a decreasing subsequence of (16,15,10,5,4). Show that the statement in the second paragraph is true for all sequences of 17 distinct integers.
  • 0

#2 alanklm

alanklm

    Junior Member

  • Members
  • PipPip
  • 20 posts

Posted 02 January 2010 - 10:49 AM

Gm.
17, 5. Strange dependence...

bushindo, Is solution simple enough?
  • 0

#3 magician

magician

    Advanced Member

  • Members
  • PipPipPip
  • 135 posts

Posted 02 January 2010 - 04:33 PM

I think I have a solution, but if everyone else is like me, a spoiler button is like a big sign saying "click here", so I'll hold off for a bit and just give a hint.

Spoiler for something to note

  • 0

#4 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 03 January 2010 - 03:14 AM

Spoiler for as I recall

  • 0

#5 bushindo

bushindo

    Senior Member

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

Posted 03 January 2010 - 06:36 PM

Spoiler for as I recall


That's some childhood you got, maybe it's a polish thing. I got mostly spanks on my mother's knee. I'll supplement the hint that magician gave earlier

Spoiler for

  • 0

#6 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 04 January 2010 - 10:55 PM

Well, it seems nobody wants to provide a proof so
Spoiler for here's mine

Edited by superprismatic, 04 January 2010 - 10:58 PM.

  • 0

#7 bushindo

bushindo

    Senior Member

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

Posted 05 January 2010 - 12:12 AM

Well, it seems nobody wants to provide a proof so

Spoiler for here's mine


That's a nice proof. I didn't think of that. Here's a clumsier proof using induction
Spoiler for

Edited by bushindo, 05 January 2010 - 12:17 AM.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users