MathDB

Let a set

S

of 2004 points in the plane be given, no three of which are collinear. Let

{\cal L}

denote the set of all lines (extended indefinitely in both directions) determined by pairs of points from the set. Show that it is possible to colour the points of

S

with at most two colours, such that for any points

p,q

S

, the number of lines in

{\cal L}

which separate

p

from

q

is odd if and only if

p

and

q

have the same colour. Note: A line

\ell

separates two points

p

and

q

p

and

q

lie on opposite sides of

\ell

with neither point on

\ell

Problem Statement