2003 IMO Problems/Problem 1
is the set . Show that for any subset of with elements we can find distinct elements of , such that the sets are all pairwise disjoint.
Consider the set . There are at most elements in . Two sets and have nonempty intersection if and only if is in . So we need to choose the elements in such a way that we do not use a difference from . Now select these elements by induction. Choose one element arbitrarily. Assume that elements, , are already chosen. An element that is already chosen prevents us from selecting any element from the set . Thus after elements are chosen, at most elements are forbidden. Hence we can select one more element.
|2003 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|