Five points are given in space, no four of which are coplanar. Each of the segments connecting two of them is painted in white, green or red, so that all the colors are used and no three segments of the same color form a triangle. Prove that among these five points there is one at which segments of all the three colors meet.
Problem
Source: Bulgaria 1981 P1
Tags: combinatorics, geometry, combinatorial geometry, graph theory
14.09.2024 17:02
Return to: Let's assume that all three colors meet at no point. *Let's prove that three line segments of the same color cannot meet at a single point Let's label each of the five points A, B, C, D, and E. Let's suppose by the regression method that A meets three white line segments. Without losing its generality, let's say that the three line segments are AB,AC,AD. Then, BC, CD, and DB cannot be white line segments according to the conditions in question. According to the Pigeonhole Principle, there is a point where all three colors meet because there are two remaining colors, three line segments are not the same, and the three line segments cannot be met at a single point. Since this is contradictory by the first assumption, three line segments of the same color cannot be met at a single point. Therefore, according to the first assumption and the above facts, there should be two line segments with two colors at a point (1) Let's say the number of white, green, and red lines is w,g,r, respectively The total number of line segments is w+g+r=2x5=10, so it is 10. According to the Pigeonhole Principle, one of w,g,r is equal to or less than 3. Let w<=3 without losing its generality. If AB is white without losing its generality, there must be one line segment connected to A and B by (1). However, since there are no more than three white line segments, the two line segments must meet at one point. Let C denote the point without losing generality. Then ABCs become white triangles and contradict the conditions in question. Because the first assumption becomes contradictory, there is a point where all three colors meet by the regression method.