pow:problem7 [Department of Mathematics and Statistics, Binghamton University]

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

User Tools

Site Tools

−Sidebar

Page Tools