Consider 9 points in space, no 4 coplanar. Each pair of points is joined by a line segment which is colored either blue or red or left uncolored. Find the smallest value of n 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
by Gerhard Wöginger
We show that for n = 32 we can find a coloring without a monochrome triangle. Take two squares R1R2R3R4 and B1B2B3B4. Leave the diagonals of each square uncolored, color the remaining edges of R red and the remaining edges of B blue. Color blue all the edges from the ninth point X to the red square, and red all the edges from X to the blue square. Color RiBj red if i and j have the same parity and blue otherwise.
Clearly X is not the vertex of a monochrome square, because if XY and XZ are the same color then, YZ 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 RiRjBk and BiBjRk. But if i and j have the same parity, then RiRj is uncolored (and similarly BiBj), whereas if they have opposite parity, then RiBk and RjBk have opposite colors (and similarly BiRk and BjRk).
It remains to show that for n = 33 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 6 points must all be colored. Take one of these, X. At least 3 of the 5 edges to X, say XA, XB, XC must be the same color (say red). If AB is also red, then XAB is monochrome. Similarly, for BC and CA. But if AB, BC and CA are all blue, then ABC is monochrome.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
2 Sep 1999