Let A be a set with n elements. Let C be a collection of distinct subsets of A…
2005
Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S1 and S2 in C, either S1 ⊂ S2 or S2⊂ S1. What is the maximum cardinality of C?
- A.
n
- B.
n + 1
- C.
2(n-1) + 1
- D.
n!
Attempted by 562 students.
Show answer & explanation
Correct answer: B
Key idea: in any family of subsets totally ordered by inclusion, the sizes of the sets must be strictly increasing.
Upper bound: If S1 ⊂ S2 ⊂ ... ⊂ Sk is a chain, then |S1| < |S2| < ... < |Sk|, so these are k distinct integers between 0 and n. Therefore k ≤ n+1.
Construction (attaining the bound): Enumerate elements of A as a1, a2, ..., an and consider the chain ∅, {a1}, {a1,a2}, ..., {a1,a2,...,an} = A. This chain has n+1 subsets and is totally ordered by inclusion.
Conclusion: The maximum cardinality of such a collection is n+1.
A video solution is available for this question — log in and enroll to watch it.