Maths Olympiad Prep

Library / /4 of 6

Combinatorics Difficulty 5.7 AIME, harder Prove it Brazil

XX has nn elements. F\mathcal{F} is a family of subsets of XX 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 XX with at least 2n\lfloor\sqrt{2n}\rfloor members which does not contain any members of F\mathcal{F}.

Solution

Let YY be a maximal subset of XX in the sense that if one adjoins another element from XX in YY then it will contain a subset from F\mathcal{F}. Define f:XY(Y2)f: X \setminus Y \to \binom{Y}{2}, where (Y2)\binom{Y}{2} is the family of 2-subsets from YY, with f(x)=Af(x) = A if A{x}A \cup \{x\} is one of the sets from F\mathcal{F}; if there is more than one set, choose any of them. ff is an injective function, because if f(x1)=f(x2)=Bf(x_1) = f(x_2) = B then B{x1}B \cup \{x_1\} and B{x2}B \cup \{x_2\} would be in F\mathcal{F} and these two sets would have more than one element in their intersection. Thus, by the injective principle,
XY(Y2)    nYY(Y1)2    Y12+2n+14 |X \setminus Y| \le \binom{|Y|}{2} \iff n - |Y| \le \frac{|Y|(|Y| - 1)}{2} \iff |Y| \ge -\frac{1}{2} + \sqrt{2n + \frac{1}{4}}
Let 2n=k\lfloor\sqrt{2n}\rfloor = k. We need to prove that 12+2n+14>k1-\frac{1}{2} + \sqrt{2n + \frac{1}{4}} > k - 1 in order to prove that Y>k1    Yk|Y| > k - 1 \iff |Y| \ge k. But this is only a small computation:
12+2n+14>k1    2n+14>k2k+14    2n>k2k,-\frac{1}{2} + \sqrt{2n + \frac{1}{4}} > k - 1 \iff 2n + \frac{1}{4} > k^2 - k + \frac{1}{4} \iff \sqrt{2n} > \sqrt{k^2 - k},
which is true because 2nk>k2k\sqrt{2n} \ge k > \sqrt{k^2 - 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 and solution reproduced as published; topic and difficulty added by this site.