MathDB
About n^2+1 intervals - Show that a subset exists

Source: IMO LongList 1979 - P14

May 29, 2011
combinatorics proposedcombinatorics

Problem Statement

Let SS be a set of n2+1n^2 + 1 closed intervals (nn a positive integer). Prove that at least one of the following assertions holds:
(i) There exists a subset S′S' of n+1n+1 intervals from SS such that the intersection of the intervals in S′S' is nonempty.
(ii) There exists a subset S′′S'' of n+1n + 1 intervals from SS such that any two of the intervals in S′′S'' are disjoint.
Back to ProblemsView on AoPS