1983 USAMO Problems/Problem 3

Problem

Each set of a finite family of subsets of a line is a union of two closed intervals. Moreover, any three of the sets of the family have a point in common. Prove that there is a point which is common to at least half the sets of the family.

Solution

Let us first see that this works for anything less than three sets.

Obviously, due to the second condition given, they all share at least one point in common.

Now, let us see that it works for three or more sets.

First, take any three of the subsets in the family of sets.

Let them be A, B, and C. We know that they share at least one point in common. Let us take the pair of segments that have the shortest length when you take the union of the pair. Let us denote this segment D. Evidently, if you take any other set of points, it must intersect D at least at one point. In order to minimize the number of intersections between the other varying segments, we must have at close to 1/2 of the remaining segments as possible intersecting each other. However, if we note, putting them that way forces at least 1/2 of the segments in each section.

See Also

1983 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.