Maths Olympiad Prep

Library / /6 of 8

Combinatorics Difficulty 5.4 AIME, harder Prove it Brazil

Given a set of nn elements, find the largest number of subsets such that no subset is contained in any other.

Solution

Let AA have nn elements. The number of sequences of chains
S1S2Sn1A S_1 \subset S_2 \subset \dots \subset S_{n-1} \subset A
such that Si=i|S_i| = i is n!n!: for each permutation (a1,a2,,an)(a_1, a_2, \dots, a_n) of elements from AA let Si=Si1{ai}S_i = S_{i-1} \cup \{a_i\}.

Fix a subset BB of AA. If B=k|B| = k, then the chains containing BB
S1S2BSn1A S_1 \subset S_2 \subset \dots \subset B \subset \dots S_{n-1} \subset A
is k!(nk)!k!(n-k)!, because there are k!k! choices for S1,,Sk1S_1, \dots, S_{k-1} and (nk)!(n-k)! choices for Sk+1,,Sn1S_{k+1}, \dots, S_{n-1}.
If BB and BB' are such that B⊄BB \not\subset B' and B⊄BB' \not\subset B, then every pair of chains, one containing BB and other containing BB', are disjoint. So if B1,B2,,BmB_1, B_2, \dots, B_m are subsets such that Bi⊄BjB_i \not\subset B_j and Bj⊄BiB_j \not\subset B_i then, denoting Bi=mi|B_i| = m_i,
i=1mmi!(nmi)!n!    i=1n1(nmi)1 \sum_{i=1}^{m} m_i!(n - m_i)! \le n! \iff \sum_{i=1}^{n} \frac{1}{\binom{n}{m_i}} \le 1
The maximum value of (nm)\binom{n}{m} is (nn2)\binom{n}{\lfloor \frac{n}{2} \rfloor}. Hence
i=1m1(nmi)1    i=1m1(nn2)1    m(nn2) \sum_{i=1}^{m} \frac{1}{\binom{n}{m_i}} \le 1 \implies \sum_{i=1}^{m} \frac{1}{\binom{n}{\lfloor \frac{n}{2} \rfloor}} \le 1 \iff m \le \binom{n}{\lfloor \frac{n}{2} \rfloor}

One example with m=(nn2)m = \binom{n}{\lfloor \frac{n}{2} \rfloor} is considering all subsets with n2\lfloor \frac{n}{2} \rfloor elements.

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.