recategorized by
1,004 views
7 votes
7 votes

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
recategorized by

1 Answer

7 votes
7 votes

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*}$

edited by
Answer:

Related questions