1,593 views
A teacher gives a multiple choice quiz that has 5 questions, each with
4 possible answers: a, b, c,d What is the minimum number of students that
must be in the class in order to guarantee that at least 4 answer sheets will be
identical?

how to do this problem

suppose n are the pigeons and m are pigeons hole then at least $\left \lfloor \frac{n-1}{ m} \right \rfloor+1$ pigeons will occupy the same pigeonholes

here n is total no. of students and m are total no. of sheets

so m =$4^5$

$\left \lfloor \frac{n-1}{ m} \right \rfloor+1$=4

put the value ,you will get n=3073

let me know ,if i do wrong??

u are correct @Prateek Raghuvanshi

@prateek i am not getting intution behind it please give me reference so that i can read it

METHOD 1.

$\rightarrow$Total no. of attempts combination possible for a student (= no. of holes =m)

= For each question he can choose any 1 of the 4 options and there are 5 such questions

$= 4*4*4*4*4$

$= 1024.$

$\rightarrow$ We need to find no. of students (= no. of pigeons = n)

$\rightarrow$ It is given that  at least $4$ answer sheets will be identical (= no. of pigeons that share the same hole should be at least 4.)

According to pigeon hole principle ,

$\left \lfloor \frac{(n-1)}{m} \right \rfloor+1=4$

$\Rightarrow$ $\left \lfloor \frac{(n-1)}{1024} \right \rfloor =3$

$\Rightarrow n-1 =3 *1024=3072$

$\Rightarrow n=3073$

METHOD 2.

In total there are $4*4*4*4*4=1024$ combination of options selection possible and a student will choose any one combination out of it.

Questions is asking how many students should be there so that atleast $4$ of them selects the same combination.

suppose $1024$ students comes and pick $1024$ unique combinations.

then another $1024$ students come and pick $1024$ unique combinations

then another $1024$ students come and pick $1024$ unique combinations.

So uptil here each combination is selected by $3$ students  and total students are $1024+1024+1024 = 3072.$

Now if a student comes and select a combination i.e. select any one of $1024$ combinations then we will have $1$ combination that is selected by $4$ student.

so minimum students required $= 3072+1 = 3073$

by

@Satbir

Can you guide me a little that how 1024 is equivalent to no. of holes for the equation. Getting difficult to visualize why this has been taken as holes.

Thank you.

check method 2 in my answer.

@Satbir

fantabulous :)

Thanks man.

1
990 views