TIFR CSE 2018 | Part A | Question: 6

Question

What is the minimum number of students needed in a class to guarantee that there are at least $6$ students whose birthdays fall in the same month ?

• A. $6$
• B. $23$
• C. $61$
• D. $72$
• E. $91$

Comments

The concept of the Pigeonhole principle is kind of similar to the concept of deadlock where we need to calculate a minimum number of resources.

Answer 1

Using pigeonhole principle: With $n$ pigeon and $m$ holes atleast $p$ pigeo will be on $m$ holes are:

$\frac{n-1}{m} +1 =p$

$n- 1 +12 =6\times 12$

$n- 1  = 72- 12=60$

$n= 60+1=61$

Correct Answer: $C$

Comments

this concept something like deadlock condition....if one of the process satisfy (at least condition)  then no more deadlock

---

@VIDYADHAR SHELKE 1

Yes, also I don't think you have to remember any formula for this question.

It's very logical.

You have $12$ months. So if there are 5 students born in each month in the worst case then you get $\mathbf{12\times5 = 60}$ but you need a guarantee of at least $6$ students whose b'day fall in the same month. $\therefore$ Add $\mathbf{+1}$ more.

So answer $=\mathbf{12\times5 + 1 = 61}$

Answer 2

Option C

Pigeon hole principle:

$\left \lceil \frac{N}{12} \right \rceil$=6

N=61

Answer 3

Jan	Feb	March	April	May	June	July	Aug	Sept	Oct	Nov	Dec
${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$	${\color{DarkRed} S}$
${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$	${\color{DarkOrange} S}$
${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$	${\color{Green} S}$
${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$	${\color{Magenta} S}$
${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$	${\color{Teal} S}$

Procedure :-

select $12$ students and then put them in $1$ slot each like $1^{st}$ Jan $, 2^{nd}$ in Feb$, 3^{rd}$ in March and so on.

repeat the above step $5$ times.

so total students selected till now $= 12\times 5 =60$ and in each month we have $5$ students.

now if we select $1$ more student then his birthday can be in any of the given $12$ months.

say his birthday is in December then we can

guarantee that there are at least $6$ students whose birthdays fall in the same month

so total students required $= 60 +1 =61.$

Answer 4

$\mathbf{\underline{Answer:C}}$

$\mathbf{\underline{Intuitive \;Answer:}}$

It's very logical.

You have $\mathbf{12}$ months. So if there are $\mathbf5$ students born in each month in the worst case then you get $\mathbf{12\times5 = 60}$ but you need a guarantee of at least $\mathbf 6$ students whose b'day fall in the same month.

$\therefore$ Add $\mathbf{+1}$ more.

So answer $=\mathbf{12\times5 + 1 = 61}$