4

Part of 2001 South africa National Olympiad

Problems(1)

2n blue and red points

Source: South Africa 2001

n

n

blue points on a plane are given so that no three of the

2n

points are collinear. Prove that it is always possible to split up the points into

n

pairs, with one red and one blue point in each pair, so that no two of the

n

line segments which connect the two members of a pair intersect.

inductioncombinatorial geometryextremal principlecombinatorics unsolvedcombinatorics