MathDB

In the plane are given

n^2 + 1

points, no three of which lie on a line. Each line segment connecting a pair of these points is colored by either red or blue. A path of length

k

is a sequence of

k

segments where the end of each segment (except for the last one) is the beginning of the next one. A path is simple if it does not intersect itself. Prove that there exists a monochromatic simple path of length

n

Problem Statement