### Sidebar

pow:problem7

Problem 7 (due Monday, May 11)

Let $S$ be a finite set with $n$ elements. What is the largest possible number $k$ such that one can choose $k$ non-empty subsets of $S$ so that for any two of these subsets, either they are disjoint or one is contained in the other.

This problem was solved by only one participant: Yuqiao Huang. The answer to the problem is $2n-1$. Both our original solution and Yuqiao's solution prove this by induction on $n$, but the inductive arguments are different. Detailed solutions are discussed in the following link Solution