1992 IMO Problems/Problem 3
Problem
Consider nine points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of such that whenever exactly n edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.
Solution
We show that for we can find a coloring without a monochrome triangle.
Take two squares
and
. Leave the diagonals of each square uncolored, color the remaining edges of
red and the remaining edges of
blue. Color blue all the edges from the ninth point
to the red square, and red
all the edges from
to the blue square. Color
red if
and
have the same parity and blue otherwise.
Clearly
is not the vertex of a monochrome square, because if
and
are
the same color then,
is either uncolored or the opposite color. There is no triangle within the red square or the blue square, and hence no monochrome triangle. It remains to consider triangles of the form
and
But if
and
have the same parity, then
is uncolored (and similarly
), whereas if
they have opposite parity, then
and
have opposite colors (and similarly
and
).
It remains to show that for
we can always find a monochrome triangle.
There are three uncolored edges. Take a point on each of the uncolored edges.
The edges between the remaining
points must all be colored. Take one of
these,
At least
of the
edges to
, say
,
,
must be the same color
(say red). If
is also red, then
is monochrome. Similarly, for
and
But if
,
and
are all blue, then
is monochrome.
See Also
1992 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |