MathDB

Coloring the points in the plane

Source: IMO Longlist 1992, Problem 20

September 1, 2010

graph theorycombinatoricsExtremal combinatoricsExtremal Graph TheoryColoringIMO ShortlistIMO Longlist

Problem Statement

Let

X

and

Y

be two sets of points in the plane and

\alpha

be a set of segments connecting points from

\beta

and

(\alpha \neq \beta)

. Let

k

be a natural number. Prove that the segments from

M

can be painted using

k

colors in such a way that for any point

x \in X \cup Y

and two colors

\alpha

and

\beta

(\alpha \neq \beta)

, the difference between the number of

\alpha

-colored segments and the number of

\beta

-colored segments originating in

X

is less than or equal to

1

.

Back to Problems View on AoPS