633 views

Consider a family $\mathcal{F}$ of subsets of $\{1, 2, \dots , n\}$ such that for any two distinct sets $A$ and $B$ in $\mathcal{F}$ we have: $A \subset B$ or $B \subset A$ or $A \cap B = \emptyset$. Which of the following statements is TRUE? (Hint: what does the Venn diagram of this family look like?)

1. $\mid \mathcal{F} \mid \leq 2n$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2n$
2. $\mid \mathcal{F} \mid \leq n^2$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =n^2$
3. $\mid \mathcal{F} \mid \leq 2n^2$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2n^2$
4. $\mid \mathcal{F} \mid \leq 2^{n-1}$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n-1}$
5. None of the above

Is it 2n ????
Official ans given A..please explain

This is what I thought ..please correct if wrong !  $\text{Assuming } \;\;\ \{1, 2, \dots , 4\}$

With following recurrence relation:

\begin{align*} f(n) = 2+ f(n-1) \;\; n\geq 2 \text{ and } \;\;\ f(1) = 2 \end{align*}

by

This is not the only maximal family $F$. $F_{MAX}$ is not unique.
$\phi$ is considered only once and in the base case $f(1)$
Very good solution.
Why are only subsequeces considered here ? Why not subsets like {1,3} ? Where is it specified that subsets shouldn’t be considered ?