X has n elements. F is a family of subsets of X 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 X with at least ⌊2n⌋ members which does not contain any members of F.
Solution
Let Y be a maximal subset of X in the sense that if one adjoins another element from X in Y then it will contain a subset from F. Define f:X∖Y→(2Y), where (2Y) is the family of 2-subsets from Y, with f(x)=A if A∪{x} is one of the sets from F; if there is more than one set, choose any of them. f is an injective function, because if f(x1)=f(x2)=B then B∪{x1} and B∪{x2} would be in F and these two sets would have more than one element in their intersection. Thus, by the injective principle, ∣X∖Y∣≤(2∣Y∣)⟺n−∣Y∣≤2∣Y∣(∣Y∣−1)⟺∣Y∣≥−21+2n+41 Let ⌊2n⌋=k. We need to prove that −21+2n+41>k−1 in order to prove that ∣Y∣>k−1⟺∣Y∣≥k. But this is only a small computation: −21+2n+41>k−1⟺2n+41>k2−k+41⟺2n>k2−k, which is true because 2n≥k>k2−k.
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.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.