GATE IT 2005 | Question: 33

Question

Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 \subset S_2$ or $S_2\subset S_1$. What is the maximum cardinality of $C?$

• A. $n$
• B. $n+1$
• C. $2^{n-1} + 1$
• D. $n!$

Comments

@MSG1999 Correct Now. 

---

For n element set, we create subsets of size 0, 1, 2, 3, 4 till n.

The pattern we can observe after taking some small examples is that we can select exactly 1 subset from each of the sizes for C.

Variation on this question could be number of collection C possible.

---

Note : Amazing concept "TOSET" you will get in my answer .

Proof and Intuition based Explanation

https://gateoverflow.in/3779/gate-it-2005-question-33?show=533199#c533199

 

 

 

Answer 1

The longest chain must start at the smallest subset ($\emptyset$) and end at the largest ($A$).

To maximize the number of subsets, we add one element at a time.

Example for $n=2$: $\emptyset \subset \{a\} \subset \{a,b\}$ has 3 subsets.

In general: $\emptyset \subset \{a_1\} \subset \{a_1,a_2\} \subset \dots \subset \{a_1,\dots,a_n\}$ has $n+1$ subsets.

Answer 2

Here let n=2 A = {1, 2}
All subsets formed by A are: – {}, {1}, {2}, {1,2}.
C is a collection of distinct subsets such that for any S1, S2 either S1⊂S2 or S2⊂S1.
So for C, {} null set can be included always since it null. set is a subset of every set.
We can choose one from either {1} or {2}, {1,2} can be included to maximise the cardinality.
So, here 1) If {1} is chosen then C = {}, {1}, {1,2} here every set is subset of other.
2) If {2} is chosen then C = {}, {2}, {1,2} here also every set is subset of other.

So, answer should be 2 but it includes empty set also therefore the maximum cardinality of C is 3.

Answer 3

Consider an example:
Let A = {a, b, c}, here n = 3
Now, P(A) = {Ø, {a}, {b}, {c}, {a,b}, {b,c}, {{a}, {a,b,c}}
Now C will be contain Ø (empty set) and {a,b,c} (set itself) as Ø is the subset of every set. And every other subset is the subset of {a,b,c}.
Now taking the subset of cardinality, we an take any 1 of {a}, {b}, {c} as none of the set is subset of other.
Let's take {2}
→ Now taking the sets of cardinality 2 -{a,b}, {b,c}
→ {b} ⊂ {a,b} and {b,c} but we can't take both as none of the 2 is subset of the other.
→ So let's take {c,a}.
So, C = {Ø, {b}, {b,c}, {a,b,c}}
→ So, if we observe carefully, we can see that we can select only 1 set from the subsets of each cardinality 1 to n
i.e., total n subsets + Ø = n + 1 subsets of A can be there in C.
→ So, even though we can have different combinations of subsets in C but maximum cardinality of C will be n+1 only.

Answer 4

$\text{A is set containing n numbers}$

$\text{P is the power-set of A}$

$\text{We have to chose 1 element each from each k- element set where k lies from 1 to n}$

$\text{When we do that, we chose PHI from phi, {1} from {1},{2},{3},...{n}} i.e. singleton set}$

$\text{likewise we select one each from all k elements sets}$

$\text{So, the right answer is n+1}$

 

Answer 5

(B)

Explanation: Here let n=2

A = {1, 2}
All subsets formed by A are: –   {}, {1}, {2}, {1,2}.
C is a collection of distinct subsets such that for any S1, S2 either S1⊂S2 or S2⊂S1.

So for C, {} null set can be included always since it null. set is a subset of every set.
We can choose one from either {1} or {2}, {1,2} can be included to maximise the cardinality.
So, here 1) If {1} is chosen then C = {}, {1}, {1,2} here every set is subset of other.
2) If {2} is chosen then C = {}, {2}, {1,2} here also every set is subset of other.

So, answer should be 2 but it includes empty set also therefore the maximum cardinality of C is 3.

so n+1 is the answer

Comments

why we need to choose only one element from C having the same cardinality?

 

A= {1,2}

P(A)  =  { phi, {1] ,{2} ,{1,2} }

C  = {   phi, {1} ,{1,2}  }  --> here why we cannot choose {2}, 

the question specifies distinct subsets and {1} and {2} are distincts , then why aren't we choosing {2} ?

Answer 6

Is it right approach?