Results 1 to 3 of 3

Math Help - Combinatorics

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    23

    Combinatorics

    I require hints on how to approach this DM problem:

    Given an integer k, show that there exists an integer n such that for any set P of n points in the plane, either P has a subset
    of k points that all lie on the same line, or P has a subset of k points such that no three of them lie on the same line.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by DeRSeD View Post
    I require hints on how to approach this DM problem:

    At the risk of being completely wrong / telling something trivial - this question appears to be one of the applications of Ramsey Theory. Just in case that helps.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by DeRSeD View Post
    I require hints on how to approach this DM problem:
    See the solution to problem 4 on this link:

    http://www.cs.princeton.edu/courses/...final03sol.pdf
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Statistics Forum
    Replies: 4
    Last Post: December 2nd 2008, 02:27 PM

Search Tags


/mathhelpforum @mathhelpforum