GATE Mechanical 2024 | GA | Question: 7

Question

How many combinations of non-null sets $\text{A, B, C}$ are possible from the subsets of $\{2,3,5\}$ satisfying the conditions: (i) $\mathrm{A}$ is a subset of $\mathrm{B}$, and (ii) $\mathrm{B}$ is a subset of $\mathrm{C}$ ?

• A. $28$
• B. $27$
• C. $18$
• D. $19$

Comments

This question was marks to all (MTA) . The correct answer should be 37 .

Answer 1

Combinations of non-null sets A, B, C are possible from the subsets of {2,3,5} satisfying the conditions:  $A\subseteq B\subseteq C= 4^3$

$ \text{ There are 3 elements and each element have these four choices}\left\{\begin{matrix}
\text{Not present in all sets} \\
\text{Present in Only set C}\\
\text{Present in set C and set B}\\
\text{Present in all sets}
\end{matrix}\right.$

(Similar Method is answered here: https://gateoverflow.in/357487/?show=357825#a357825 )

 

Here the question is about non-null sets A, B, C $\Rightarrow 4^3 - (\text{Any set is Empty})$

Consider A = $\phi$, then we need to calculate number of possible sets of B and C.

Universal set = {2,3,5} contains 3 elements $\Rightarrow $B has $2^3$ possible choices and for each possible B set, we need to calculate possible sets of C.

 

As $B\subseteq C$, the elements present in the B, should be present in C. Remaining elements of Universal set has two choices; present in C or not present in C. 

$if\; B= \phi \text{(number of elements in B = 0)}\Rightarrow \text{number of possible sets for C = } 2^{n-0}=2^3$

$if\; B= \{1\} \text{(number of elements in B = 1)}\Rightarrow \text{number of possible sets for C = } 2^{n-1}=2^2$

$if\; B= \{2\} \text{(number of elements in B = 1)}\Rightarrow \text{number of possible sets for C = } 2^{n-1}=2^2$

$if\; B= \{3\} \text{(number of elements in B = 1)}\Rightarrow \text{number of possible sets for C = } 2^{n-1}=2^2$

$if\; B= \{1,2\} \text{(number of elements in B = 2)}\Rightarrow \text{number of possible sets for C = } 2^{n-2}=2^1$

$if\; B= \{1,3\} \text{(number of elements in B = 2)}\Rightarrow \text{number of possible sets for C = } 2^{n-2}=2^1$

$if\; B= \{2,3\} \text{(number of elements in B = 2)}\Rightarrow \text{number of possible sets for C = } 2^{n-2}=2^1$

$if\; B= \{1,2,3\}\text{(number of elements in B = 3)}\Rightarrow \text{number of possible sets for C = } 2^{n-3}=2^0$

 

To sum of all the above, it is like

$\binom{n}{0}*2^{n}+\binom{n}{1}*2^{n-1}+\dots +\binom{n}{r}*2^{n-r} \dots + \binom{n}{n}*2^{0} = (1+2)^n=3^n= 3^3=27$

$\therefore when \;A=\phi \text{, possible sets of B and C are 27. }$

$ \text{ Alternatively you can think like, when A = } \phi \text{, there are 3 elements and each element have these three choices}\left\{\begin{matrix}
\text{Not present in both C and B} \\
\text{Present in Only set C}\\
\text{Present in set C and set B}\\
\end{matrix}\right.$

$\text{Please note that B=}\phi \text{ and C = }\phi \text{ possibilities are also covered in this 27}$

 

 

Final answer = $4^3-3^3 = 37$

---

Extra Info:

if there are 4 sets instead of 3 in the question, $A\subseteq B\subseteq C \subseteq D, then\; answer =5^3-4^3$

$\binom{n}{0}*3^{n}+\binom{n}{1}*3^{n-1}+\dots +\binom{n}{r}*3^{n-r} \dots + \binom{n}{n}*3^{0} = (1+3)^n=4^n= 4^3$

$\therefore when \;A=\phi \text{, possible sets of B, C and D are 64.}$

Comments

I have a doubt of why is it MTA 

I dont think so its 37 and the answer is 27 because in the question this exact line means "from the subsets of  {2,3,5,} satisfying" which would mean you can only form A B and C from the all the possible subsets of the sample (i.e   {2,3,5,} ).

And then chose a set for A B and C. 

The reason for MTA is what then if this is true and if not can you prove my argument wrong .

---

How you are getting 27 ?

Write an explanation for that. Then someone will comment where your argument going in wrong direction.

Answer 2

the anwer is 37 and it was an MTA.
here it goes

for n numbers in a set total number of subsets are 2^n which includes null set.
so here total 3- single digit subsets, 3- two digit subsets, 1 -3 digit subset.

if c is 3 digit subset and

  if B is 3 digit subset we get total 7 combinations
  if B is 2 digit subset we get total 9 combinations

  if B is 1 digit subset we get total of 3 combinations

hence in this 19

if c is a 2 digit subset and

  if B is a 2 digit subset then we get 9 combinations

  if B is a 1 digit subse then we get 6 combinations

hence in this 15

if c is a 1 digit subset

then we get 3 combinations

 

hence total 19+15+3 = 37