PigeonholePrinciple ColoringMethod Putnam Basic
1953


Problem - 2748
There are $6$ points in the $3$-D space. No three points are on the same line and no four points are one the same plane. Hence totally $15$ segments can be created among these points. Show that if each of these $15$ segments is colored either black or white, there must exist a triangle whose sides are of same color.

Pickup any point $A$. There are five lines connecting this point. By the pigeonhole principle, at least three of these edges are of the same color. Without loss of generality, let's assume these three lines are white and they connect to point $B$, $C$, and $D$, respectively.

Now, consider the color of line $BC$, $CD$, and $DB$. If any of them is white, a white triangle is found by combining point $A$. Otherwise, if all of them are black, a black triangle $BCD$ is found.

Hence, the claim holds.


report an error