A finite set of segments on a line has the following property: In any subset of $1998$ segments there are two having a common point. Show that there exist $1997$ points on the line such that each segment contains at least one of these points.
Problem
Source: Ukraine 1998 Grade 10 P3
Tags: geometry, combinatorics, combinatorial geometry
08.06.2021 23:13
Arrange the line horizontally, so we can refer to a certain endpoint of every segment as "left" and the other as "right". Let $S$ be the largest set of segments such that no two segments in $S$ share an element, and let $|S| = c \leq 1997$. By definition, every other segment intersects at least one element of $S$. For each element $i$ of $S$, if there is a segment completely contained inside of $i$ that does not contain any other segments, replace $i$ with that segment in $S$, and then paint every segment in $S$ green. We claim that we can highlight a single point in every element of $S$, so that every segment contains at least one point. Let $a$ be the leftmost green segment in $S$. Denote the highlighted point inside of $a$ $P_a$. There are distinct three ways in which a segment $b$ outside of $S$ may intersect with $a$: $b$ contains $a$, $b$ contains $a$'s right endpoint but not its left, or $b$ contains $a$'s left endpoint but not its right. The segments of the first kind can be completely ignored: $P_a$ is obviously in them. For simplicity, call a segment of the second kind "right wing", and call a segment of the third kind "left wing". Right and left wing segments of a segment in $S$ can only intersect one other segment in $S$ before completely enveloping some segment in $S$ and becoming irrelevant. Thus, call a segment that intersects only one segment in $S$ "tribal", and we note that by definition all of $a$'s left wing segments are tribal. We note that if a tribal right wing segment of $a$ must intersect every tribal left wing segment of $a$, since otherwise we could replace $a$ with those two non-intersecting tribal segments, and we would have a segment larger than $S$ with no pairwise intersections. Thus, the rightmost left endpoint out of all tribal right wing segments of $a$ is farther to the left than the leftmost right endpoint out of all tribal left wing segments of $a$, since the segments those endpoints belong to intersect. Every other tribal segment extends past this point and therefore includes it, so it is always possible to place $P_a$ so that all tribal segments contain it. We then color $a$ yellow. We can repeat this process until all of $S$ is yellow, since this operation can be performed on every leftmost green segment. As every segment intersects some segment in $S$, every segment contains the highlighted point of at least one of the $c$ yellow segments. As $c \leq 1997$, we are done.