GATE2011 MN: GA-59

Question

In how many ways $3$ scholarships can be awarded to $4$ applicants, when each applicant can receive any number of scholarships?

• A. $4$ 
• B. $12$ 
• C. $64$ 
• D. $81$

Comments

Question can be more specific:

• If scholarships are identical → use stars and bars → answer would be 20.

• If scholarships are distinct → use assignments with repetition → answer is 4³ = 64.

---

i did the same as i can't assume scholarships to be identical or distinct

if we assume scholarships to be identical then it follows IODB TEMPLATE :

so,number of stars=3 and number of bars=3 

number ways to we can arrage these stars and bars= 6c3=20

if we assume shcholarships to be distinct then it follows DODB TEMPLATE :

as each applicant can get any number of scholarships there could be three distributions possible:

AP1	AP2	AP3	AP4
1	1	1	0
2	1	0	0
3	0	0	0

 

There are toal 4c1*1!=4 distibutions of this kind 1 1 1 0  possible 

Number of ways to distribute like this =  4*3c1*2c1*1c1=24 ways

There aer total 4c2*2! = 12 distributions of this kind 2 1 0 0 possible

Number of ways to distribute like this = 12 * 3c2*1c1=36 ways

There are toal 4c3*1!=4 distributions of this kind 3 0 0 0  possible 

Number of ways to distribute like this =  4*3c3=4 ways

Finally ,Total number of ways to distribute 3 scholarhips to 4 applicants = 24+36+4=64 ways

Answer 1

One scholarship can be awarded to $4$ applicants in $4$ ways. Three scholarship can be awarded to

$4$ applicants in $4^{3} = 64$ ways.

(All scholarship are independent, any student can get any no of scholarships between 0 and 3)

Correct Answer: $C$

Comments

Why the option is not $4^{4}$ ??

I mean 3 scholarships available and each student can have 4 choices = {0,1,2,3}

Here 0 means the student haven’t got the scholarship and 3 means it have all the 3 scholarships.

So,   it should be   =   4 * 4 * 4 * 4   =  $4^{4}$.     (one 4 for each student)

           

---

@Kiyoshi  You are overcounting the cases. Here, we should go from the point of view of scholarships, not from the point of view of students. Suppose, if each student can have 4 choices = {0,1,2,3} then there will be cases possible like:

1) $\underbrace{S1}_{0} \quad \underbrace{S2}_{0} \quad \underbrace{S3}_{0} \quad \underbrace{S4}_{0}$

2) $\underbrace{S1}_{3} \quad \underbrace{S2}_{3} \quad \underbrace{S3}_{3} \quad \underbrace{S4}_{3}$

3) $\underbrace{S1}_{1} \quad \underbrace{S2}_{0} \quad \underbrace{S3}_{0} \quad \underbrace{S4}_{0}$

4) etc.

and these cases are not valid.

---

@Kiyoshi doubt also made me to think what if we allow students to choose one scholrahip out of three, ie., option d) 3*3*3*3 = 81. But this is wrong here's why?

If Student A1 selected shcolarship SP1, Student A2 also selected SP1, A3 also SP1, A4 also SP1. (Since each has freedom to choose one out of three scholarhips.). Now interestingly one studenet can get many scholarhips. but one scholarhip can't be distributed among many students just like an IIT seat can't be shared by 4 students. So this is wrong scenario.

On the other hand if we consider scenario that SP1 goes to A1 and SP2 goes to A1 and SP3 also goes to A1, This is possible (given in question). Since we have to select a student for a scholarship thus, we can't take the 0 case that no student is selected for a scholarhip. Its mentioned in how many way we can award these scholarhips. Therefore we have to select one student out of 4 for each scholarhip. Therefore 4C1 *4C1*4C1.

Answer 2

Added this answer for extra clarity.

Take 1^st scholarship, it can be given to any of the 4 applicants. So 4 ways.

As it is given that,

each applicant can receive any number of scholarships

An applicant can have any number of scholarships from 0 to all 3. Suppose an applicant gets all 3 scholarships, the rest of the applicants will get no scholarships.

So it is possible that the applicant having the 1^st scholarship may also get the 2^nd scholarship.

Take 2^nd scholarship, it can also be given to any of the 4 applicants. So 4 ways.

Take 3^rd scholarship, it can also be given to any of the 4 applicants. So 4 ways.

Total number of ways 3 scholarships can be given to 4 applicants = 4 * 4 * 4 = 64 ways.

Answer 3

@Kiyoshi doubt also made me to think what if we allow students to choose one scholrahip out of three, ie., option d) 3*3*3*3 = 81. But this is wrong here's why?

If Student A1 selected shcolarship SP1, Student A2 also selected SP1, A3 also SP1, A4 also SP1. (Since each has freedom to choose one out of three scholarhips.). Now interestingly one studenet can get many scholarhips. but one scholarhip can't be distributed among many students just like an IIT seat can't be shared by 4 students. So this is wrong scenario.

On the other hand if we consider scenario that SP1 goes to A1 and SP2 goes to A1 and SP3 also goes to A1, This is possible (given in question). Since we have to select a student for a scholarship thus, we can't take the 0 case that no student is selected for a scholarhip. Its mentioned in how many way we can award these scholarhips. Therefore we have to select one student out of 4 for each scholarhip. Therefore 4C1 *4C1*4C1.