1992 IMO Problems/Problem 3
Probloem
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 | ||
