MathDB
Colouring line segments using two colours

Source: ToT 2003-JO-4

June 18, 2011
graph theorycombinatorics unsolvedcombinatorics

Problem Statement

There are NN points on the plane; no three of them belong to the same straight line. Every pair of points is connected by a segment. Some of these segments are colored in red and the rest of them in blue. The red segments form a closed broken line without self-intersections(each red segment having only common endpoints with its two neighbors and no other common points with the other segments), and so do the blue segments. Find all possible values of NN for which such a disposition of NN points and such a choice of red and blue segments are possible.