1

I was trying to solve this question, yet I could not come up with a straightforward proof... it says given a set S containing 100 points on a plane, no 3 on a line, there is a convex polygon whose vertices are in the set S and that contains exactly 50 points of S (including its vertices). I don't know what to do since it has asked of us to prove "exactly" 50 points and I do not know how to guarantee that in my proof.

Is it correct to put a rubber band around them, and in each stage, let go of one of it's vertices and end up with one less than what we had, and go forward till we end up with 50 vertices covered?

gloomysunday
  • 63
  • You might want to post it as an edit, and not a comment. – Aritra Das May 13 '16 at 07:03
  • 2
    There are only finitely many directions determined by two points. Take a line not in any of these directions and with all the points on one side of the line. Move it across the points keeping the direction the same. Then it must cross points one at a time. Stop when it has crossed 50. Now take the convex hull of the points on one side of the line. – almagest May 13 '16 at 07:09

1 Answers1

4

Draw a pair of coordinate axes. There are only $\binom{100}{2}$ pairs of points, and the lines that join them have at most $\binom{100}{2}$ different slopes. Let $m$ be a number different from all of these slopes.

Imagine drawing a line of slope $m$, with all the points of $S$ on one side of the line. Move this line parallel to itself until exactly $50$ points of $S$ are on one side of the line or on the line, and $50$ points are on the other side of the line. This can be done since no line of slope $m$ can contain more than one point of $S$.

Let $T$ be either of the two sets. The convex hull of $T$ is a convex polygon with the required property.

André Nicolas
  • 507,029