PigeonholePrinciple ColoringMethod Hungary Intermediate

Problem - 2747
Show that among any $6$ people in the world, there must exist $3$ people who either know each other or do not know each other.

Let's use six dots to represent these six people. If two people know each other, we connect these two dots using a green line. Otherwise, if they do not know each other, we connect them using a red line. Then, the to-be-proved claim is equivalent to show that there must exist a triangle whose three edges are of the same color.

From any dot, there are five edges. By the pigeonhole principle, at least three of these edges are of the same color. Without loss of generality, let's assume these three edges are all green .

Now, let's consider the color of these three edges marked with question marks. If any of them is green, then we find a green triangle. If none of them is green, i.e. all of them are red, these three edges will create a red triangle. Hence, the conclusion hold regardlessly.

report an error