Thread: 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.

Originally Posted by DeRSeD

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.

Originally Posted by DeRSeD

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