1983 USAMO Problems/Problem 3
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.
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.
|1983 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|