in Others
572 views
5 votes
5 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
in Others
572 views

2 Comments

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

1 Answer

5 votes
5 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
by

4 Comments

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

Related questions