has elements. is a family of subsets of each with three elements, such that any two of the subsets have at most one element in common. Show that there is a subset of with at least members which does not contain any members of .
Solution
Let be a maximal subset of in the sense that if one adjoins another element from in then it will contain a subset from . Define , where is the family of 2-subsets from , with if is one of the sets from ; if there is more than one set, choose any of them. is an injective function, because if then and would be in and these two sets would have more than one element in their intersection. Thus, by the injective principle,
Let . We need to prove that in order to prove that . But this is only a small computation:
which is true because .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.