2,439 views
0 votes
0 votes
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

1 Answer

2 votes
2 votes

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$

edited by

Related questions

0 votes
0 votes
0 answers
1
pC asked Jan 15, 2016
1,174 views
The least num of computers required to connect 8 computers to 4 printers to guarantee 4 comp can direct]ly access 4 printer is _____1617192021
2 votes
2 votes
1 answer
2
Sammohan Ganguly asked May 25, 2018
978 views
Prove that out of hundred whole numbers one will always have $15$ of them such that the difference between any two of these $15$ numbers is divisible by $7$.
1 votes
1 votes
2 answers
3
Sammohan Ganguly asked May 25, 2018
2,798 views
Show that in a group of $n$ people there are two who have identical number of friends in that group.
2 votes
2 votes
1 answer
4
eyeamgj asked Nov 5, 2018
2,655 views
https://gateoverflow.in/13170/application-of-pigeonhole-principleWHY 14 IS ADDED ..hOW TWO SEQUENCES ARE RELATED FOR THIS ANSWER??