Separating $3n$ points on the plane by a line

Question

I am trying to solve a problem in geometry (a contest-type question), and I wondering if the following result is true. (If it is true, then it makes life much easier!)

Suppose there are $3n$ points in the plane, no three of which are collinear. Then there exists a line $L$ on the plane such that $3$ of the points lie on one side of $L$, and $3(n-1)$ of the points lie on the other side of $L$.

I am relatively confident that the assertion is true. I have drawn a lot of special cases, but general proof is out of my reach. I appreciate any hints.

Answer 1

There is only a finite number of directions parallel to a line connecting two points. Pick a different direction, and use lsp's comment.

Answer 2

I think proof by induction works. You will apply the induction hypothesis to get a line $L$ that separates $3(n-1)$ and 6 points and then since no 3 of the points are colinear by parallel translation of $L$ you get the line you want.

Answer 3

Take any line that is part of the convex hull of the points. This line includes two points, let them be $A$ and $B$, of the $3n$, and $3n-2$ points are on one side of it.

Start rotating that line, holding $A$ constant, such that $B$ is on the other side (relative to the $3n-2$ points), until it "hits" another point. (It can never hit more than one at the same time, otherwise $A$ and these would be colinear.) Take that line, move it slightly away from $B$. Voilà, your $L$, isn't it?

[edit] Alternative to the "rotate that line" intuition, the convex hull of all points except $B$ contains two lines starting from $A$, one of which is not part of the convex hull of all points including $B$. This is the line you want.

To see that you can always move a line $L'$ with $a$ points on one side, $b$ points on it and $c$ points on the other side such that the moved line has $a+b$ points on one side and none on it, find the closest among the $c$ points and the line parallel to $L'$ that is half the closest distance away from $L'$ towards that point. (As @lsp points out, this idea alone can be used to show what you want.)