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 1 of 4: Build a coloring with 32 colored edges

Previous step Next step

In plain words

Build a coloring with 32 colored edges

4+4+8+16=32

Detailed analysis

Use red vertices $R_1,\dots,R_4$ , blue vertices $B_1,\dots,B_4$ , and a ninth point $X$ . Leave the two diagonals in each square uncolored. Color the other 4 edges of the red square red and the other 4 edges of the blue square blue. Color all 8 edges from $X$ to the red square blue and from $X$ to the blue square red. Color every cross-edge $R_iB_j$ red when $i,j$ have the same parity and blue otherwise. Exactly $4+4+8+16=32$ edges are colored.