GATE2017 EC-1: GA-9

Question

There are $3$ Indians and $3$ Chinese in a group of $6$ people. How many subgroups of this group can we choose so that every subgroup has at least one Indian?

• A. $56$
• B. $52$
• C. $48$
• D. $44$

Answer 1

Number of Indian people $=3$
Number of Chinese people $=3$
Total number of people,  $n=6$

Total number of groups is basically any non-empty subset of this group of $6=2^{n}-1=2^6-1=63$

Number of groups having no Indian people $=$ Select a group out of remaining $3$ people $ = 2^3 - 1 = 7.$

$\therefore$ the number of sub-groups having at least one Indian $=63-7=56.$

Correct answer is option (A).

Comments

How to screw up?(I know because I just did :P)

Let i1, i2, i3 be Indians and c1, c2, c3 be Chinese.

First we select 1 Indian in $\binom{3}{1}$ ways and then multiply with the total subsets possible with the remaining 5 members =  $\binom{3}{1}$ * 2$^{5}$ = 3 * 32 = 96.

This is wrong because in the process of multiplying we have counted some sets twice or thrice.

Ex: select (i1) and {c1,c2,i2} = {i1,i2,c1,c2}

select (i2) and {c1,c2,i1} = {i1,i2,c1,c2} 

Clearly the above 2 sets are same but are counted twice. There are many such sets which are repeatedly counted twice and thrice.

---

It can also be done like this way…
 

Method 1 -:

Indians = {I1,I2,I3}      Chinese= {C1,C2,C3}

Required = (1 indian and (0 or 1 or 2 or 3 choices for Chinese)) + (2 indian and (0 or 1 or 2 or 3 choices for Chinese)) +((1 indian and (0 or 1 or 2 or 3 choices for Chinese)))

= 3C1 * (3C0 + 3C1 + 3C2 + 3C3) + 3C2 * (3C0 + 3C1 + 3C2 + 3C3) + 3C3 * (3C0 + 3C1 + 3C2 + 3C3)

= 3*(1+3+3+1) + 3*(1+3+3+1) + 1*(1+3+3+1)

= 24+ 24 + 8

= 56

 

Method 2 -:

Indians = {I1,I2,I3}      Chinese= {C1,C2,C3}

total 6 peoples. So total subgroups formed except null = 2^6 -1 = 63

Required =total subgroups  –  (0 indian choosen and (1 or 2 or 3 choices for Chinese))

                = 63 – ( 3C0 * ( 3C1 + 3C2 + 3C3) )

                = 63 –  1* 7

                = 56

Answer 2

Since question says we need at least one Indian. We need to consider below cases:

Case 1:
1 Indian (0 Chinese + 1 Chinese + 2 Chinese + 3 Chinese) ==> 3C1 * (3C0 + 3C1 + 3C2 + 3C3)

Case 2:
2 Indians (0 Chinese + 1 Chinese + 2 Chinese + 3 Chinese) ==> 3C2 * (3C0 + 3C1 + 3C2 + 3C3)

Case 3:
3 Indians (0 Chinese + 1 Chinese + 2 Chinese + 3 Chinese) ==> 3C3 * (3C0 + 3C1 + 3C2 + 3C3)

To find the no. of subgroups, we need to consider all the 3 cases.

no. of sub groups = 3C1 * (3C0 + 3C1 + 3C2 + 3C3) + 3C2 * (3C0 + 3C1 + 3C2 + 3C3) + 3C3 * (3C0 + 3C1 + 3C2 + 3C3)

                                = (3C0 + 3C1 + 3C2 + 3C3) * (3C1 + 3C2 + 3C3)

                                = 8 * 7

                                = 56