Differences

This shows you the differences between two versions of the page.

--- pow:problem7 [2020/05/09 22:07] – created mazur
+++ pow:problem7 [2020/05/11 17:49] (current) – mazur
@@ Line 1: / Line 1: @@
+<box 80% round orange|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.
+</box>
+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 {{:pow:2020sproblem7.pdf|Solution}}