Difference between revisions of "1983 USAMO Problems/Problem 3"
(Created page with "== 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 ...") |
(→Solution) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 3: | Line 3: | ||
== Solution == | == 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 == | == See Also == | ||
| − | {{USAMO box|year= | + | {{USAMO box|year=1983|num-b=2|num-a=4}} |
{{MAA Notice}} | {{MAA Notice}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
Latest revision as of 17:03, 15 May 2020
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. 
