GATE 2019

Question

Let U = {1, 2, ..., n} and A = {(x, X), x ∈ X and X ⊆ U}. Consider the following two
statements for |A|.

1. (i) |A| = n*$\small 2^{n-1}$

(ii) |A|= Sigma(k=1 to n) k.(nCk) 
Which of the following is correct?
(a) (i) only (b) (ii) only
(c) Both (i) and (ii) (d) None of the above

Comments

Refer here for this question:

https://gateoverflow.in/302843/Gate-cse-2019-question-5

Answer 1

Let U=$\{1,2,3\}$

All Possible subsets of U = $\{\phi,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

$A = {(x, X), x ∈ X \ and\ X ⊆ U}$

$x$ can be only $\{\phi,1,2,3\}${Considering $\phi$ also a valid $x$}

Now A can have elements like :- $\{1,\{1,2\}\}$ {Here X is $\{1,2\}$ }.

When $x=1$ , total elements in A = 4.

Similarly for $x=2$ and $x=3$ , total elements in A would be 4,4 respectively.

Therefore, total elements in A , $i.e \ |A|$ = $4+4+4 = 12$.

Not considering $x=\phi$ and $X=\phi$ since $\phi \in \phi $ is not true.
Now comparing against options ,

option (i) -> $n*2^{(n-1)}$ when n=3 , this option gives $12$ , matches.

option (ii) -> $\sum_{k=1}^{n}k*n_{C_{k}} = 1*3_{C_{1}} + 2*3_{C_{2}}+3*3_{C_{3}} = 3 + 6 +3 = 12.$

Thus both are correct.

Comments

How can x be phi ?

Phi is the subset of every set not the element of every set.

---

Question was n*2^(n-1) not n*(2n-1)

So for x= 3 it comes 12 only.

Both are equivalent

---

Both should be the answer

---

See thr given question , i couldn't see power there. Sorry , yes with power both must be the answer

---

In actual question option (i) was n*(2^(n-1))

Which is same as option (ii)

---

its $n{2^{n-1}}$

---

This was asked for how many marks?

---

correct.

And I solved full question correctly and ruined it while calculating nCk . and I marked only one as answer.

---

2marks..so i loose -2.66 here

---

@Abbas2131 $\phi$ can be taken as an element , but won't make any difference since $\phi \in \phi$ is false.

If instead of X=$\phi$ X=$\{\phi\}$ was there , it would've made a difference.

---

@Shashank Mishra 

I think this was of 1 mark only..though the question was good and seems like 2 marks :P

---

Yes, it was 1 mark

---

Hoping that u r right and i am wrong

Answer 2

Not considering x=ϕ and X=ϕ since ϕ∈ϕ is not true.

 

Comments

thank u for such detailed solution.

---

In ur first image how will u deal with |x| = 3. Justify how nC3. 3

Answer 3

I think this could be an equivalence explanation for the two options:

Option 2 says : |A|= Sigma(k=1 to n) k.(nCk) : This can be thought of as number of ways to choose k-member-team from n people and then selecting 1 among those k as the team leader. And then it sums over all k.

Option 1 says: Select 1 team leader from n people and then select k-1 other team members from remaining n-1 people which will be : n*((n-1)C(k-1)) and sum over all k here will give n*2n−1.

Answer 4

Both 1&2

Comments

Can you prove both of them are equivalent?

Did you try for n=4

---

---

Is this right??

---

@Mehul11jain don't write answers like that . Answer with clear explanation , otherwise moderators would flag it or strike it down. :)

---

ok, got it .