TIFR CSE 2016 | Part B | Question: 14

Question

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?)

• A. $\mid \mathcal{F} \mid \leq 2n$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2n$
• B. $\mid \mathcal{F} \mid \leq n^2$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =n^2$
• C. $\mid \mathcal{F} \mid \leq 2n^2$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2n^2$
• D. $\mid \mathcal{F} \mid \leq 2^{n-1}$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n-1}$
• E. None of the above

Comments

Is it 2n ????

---

Official ans given A..please explain

Answer 1

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

Comments

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 ?