Problem 3

Consider 9 points in space, no 4 coplanar. Each pair is joined by an edge colored red, blue, or left uncolored. Find the smallest

n

such that whenever exactly

n

edges are colored, there is a triangle whose three edges have the same color.

Step 4 of 4: Show 33 colored edges force a monochromatic triangle

Previous step Next step

In plain words

Show 33 colored edges force a monochromatic triangle

n\ge33

Detailed analysis

If exactly $33$ edges are colored, exactly $3$ are uncolored. Choose one point on each uncolored edge; the remaining six points have all mutual edges colored. At one of them, say $X$ , at least three of the five incident edges have one color, say red, to points $A,B,C$ . If any of $AB,BC,CA$ is red, there is a red triangle with $X$ . If none is red, all three are blue, so $ABC$ is a blue triangle. Therefore the least $n$ is $33$ .