1992 IMO Problems/Problem 3

3. 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.