The Gateway to Computer Science Excellence
+10 votes
584 views

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 ?

  1. $6$
  2. $23$
  3. $61$
  4. $72$
  5. $91$
in Combinatory by Veteran
edited by | 584 views

5 Answers

+14 votes
Best answer
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$
by Boss
edited by
+5
this concept something like deadlock condition....if one of the process satisfy (at least condition)  then no more deadlock
0

@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}$

+4 votes
Option C

Pigeon hole principle:

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

N=61
by Boss
edited by
+2 votes
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.$

by Boss
edited by
0 votes
By pigeon hole principal we can ensure that in 61 we will have atleast 6 student having birthday on same month

n=km+1 k=5, m=12
by Boss
0 votes

$\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}$

by Boss
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,914 answers
201,115 comments
118,159 users