We have finite white and finite black points that for each 4 oints there is a line that white points and black points are at different sides of this line.Prove there is a line that all white points and black points are at different side of this line.
Problem
Source: Iran 2004
Tags: combinatorial geometry, combinatorics proposed, combinatorics
pbornsztein
16.09.2004 16:54
We assume that there are at least 4 points otherwise the result may not hold Moreover, we assume that both colors are used otherwise the result is obvious.... Ok, now : Lemma 1 : There do not exist a black point which belongs to a segment whose both endpoints are white. Proof : Clearly, if B is black and belongs to the segment $[W,W']$, where $W,W'$ are white, then considering any other fourth point, a lin separating the black points from the white ones must meet the line $WW'$ between W and B, and between W' and B, which is impossible. Lemma 2 : Let $C_w$ be the convex hull of the white points. Then, there is no black point on the sides or in the interior of $C_w$. Proof. Since the number of white points is finite, $C_w$ is a convex polygon (possibily degenerated). From lemma 1, we know that there is no black point on the sides of $C_w$. Now assume that the black point $B$ is interior to $C_w$. Thus, $C_w$ is not contained in a line. Using a triangulation of $C_w$ by the diagonals from one of its vertices, we deduce that $B$ is an interior point of the triangle $WW'W''$ whose vertices are white points. Using this set of 4 points, any line which separate $B$ from the three vertices must meet two of the triangle sides, say $WW'$ and $WW''$. In that case, $W,W'$ are not on the same side of the line. A contradiction. We have a similar result of the convex hull $C_b$ of the black points. It follows that $C_w$ and $C_b$ are two disjoint convex polygons. It is now clear that we may find a separating line for these two polygons, and we are done. Pierre.