Maths Olympiad Prep

Library / Brazilian Mathematical Olympiad /62 of 120

Brazilian Mathematical Olympiad

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
S1⊂S2⊂⋯⊂Sn−1⊂A 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=Si−1∪{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
S1⊂S2⊂⋯⊂B⊂…Sn−1⊂A S_1 \subset S_2 \subset \dots \subset B \subset \dots S_{n-1} \subset A
is k!(n−k)!k!(n-k)!, because there are k!k! choices for S1,…,Sk−1S_1, \dots, S_{k-1} and (n−k)!(n-k)! choices for Sk+1,…,Sn−1S_{k+1}, \dots, S_{n-1}.
If BB and B′B' are such that B⊄B′B \not\subset B' and B′⊄BB' \not\subset B, then every pair of chains, one containing BB and other containing B′B', 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!(n−mi)!≤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 (n⌊n2⌋)\binom{n}{\lfloor \frac{n}{2} \rfloor}. Hence
∑i=1m1(nmi)≤1  ⟹  ∑i=1m1(n⌊n2⌋)≤1  ⟺  m≤(n⌊n2⌋) \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=(n⌊n2⌋)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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.