On the plane are marked $ 2005$ points, no three of which are collinear. A line is drawn through any two of the points. Show that the points can be painted in two colors so that for any two points of the same color the number of the drawn lines separating them is even. (Two points are separated by a line if they lie in different open half-planes determined by the line).
Problem
Source: Ukraine 2005 grade 10
Tags: combinatorics proposed, combinatorics
jgnr
05.06.2011 20:06
For each drawn line, mark one side with + and the other side with -. Color a point red if it lies on an even number of + regions, otherwise color it blue.
ninjaturtle
06.06.2011 07:55
Johan Gunardi wrote:
For each drawn line, mark one side with + and the other side with -. Color a point red if it lies on an even number of + regions, otherwise color it blue.
The problem with this approach is that the number of $+$ regions do not vary continuously when one travel along an edge, it may jump more than one, i may even jump an even number. Consider the following example. There are $4$ points, and one is point $P$ lying inside the triangle $ABC$. For each edge of the triangle, mark the region containing the triangle plus. Then mark the regions divided by $PA$ so that $B$ is plus, $PB$ so that $C$ is plus, and $PC$ so that $A$ is plus. Then each $A,B,C$ will all have two pluses, hence have the same color. But each pair is separated by exactly one line.
ninjaturtle
06.06.2011 08:21
For each edge $ab$ between two points, define a cross along $ab$ to be a drawn line that separates two endpoints. Claim $1$: The total number of crosses along all egdes of a triangle is always even. Proof: Each line that does not pass through any vertex of the triangle crosses either $2$ edges or no edge, hence contribute an even number of crosses. Now consider the crosses of lines that pass through exactly one of the vertices. Devide the lines in to $2002$ group of three lines, such that all lines in same group pass through a point that is not a vertex. Each group contributes either one or three crosses, depending on whether the common point lies inside or outside the triangle. There are an even number of groups, hence the total number of crosses is also even in this case. Choose a point $a$ and color red. For any $b$, color red if $ab$ has even number of crosses, blue otherwise. Claim $1$ ensures that this coloring has the desired property. In fact, we even prove that two points are of same color if and only if their edge has even number of crosses.
yunxiu
06.06.2011 17:47
Also like APMO 2004 http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=82830