GATE IT 2008 | Question: 23

Question

What is the probability that in a randomly chosen group of $r$ people at least three people have the same birthday?

• A. $1-\dfrac{365-364 \dots (365-r+1)}{365^{r}}$
• B. $\dfrac{365 \cdot 364 \dots (365-r+1)}{365^r}+ ^{r}C_{1}\cdot 365 \cdot \dfrac{364.363 \dots (364-(r-2)+1)}{364^{r+2} }$
• C. $1- \dfrac{365 \cdot 364 \dots (365-r+1)}{365^{r}} - ^{r}C_{2} \cdot 365 \cdot \dfrac{ 364 \cdot 363 \dots (364-(r-2)+1)}{364^{r-2}}$
• D. $\dfrac{365 \cdot 364 \dots (365-r+1)}{365^{r}}$

Comments

self note-

suppose there are only 3 days in an year – 1,2,3

group has 4 people – r=4

then a situation with bdays like (1,1,2,2) is valid bcz person1 has same bday with p2 , p2 has same bday with p1 , p3-p4 and p4-p3.

so total 4 person have same birthdays which is >= at least 3 person having same birthdays

Answer 1

The question is actually confusing considering the given options. It seems like they asked for probability of at least 3 people sharing birthday with someone (which is different from at least 3 having birthday on same day as there can be many pairs having birthday on same day). So, lets calculate this.

Case 1: Among $365$ people If all $r$ have birthdays on different days.
Then first one can have his birthday in $365$  ways. Second one can have in $364$ ways, and so on up to $r^{th}$ person, who can have his birthday in $(365-(r-1))$ ways.

Case 2: Among $365$ people If exactly $2$ persons have birthdays on same day.
Then we can consider these 2 persons as single entity. Then these two (assumed as first person) can have their birthday in $365$  ways.
Third person can have in 364 ways, and so on up to $r^{th}$ person, who can have his birthday in $(365-(r-2))$ ways (since 1 person is less now).

As we know,
$P_{\large\text{at least 3 with same birthday}} = 1 - \left[P_{\large\text{no two having same birthday}}+ P_{\large\text{exactly 2 having same birthday}}\right]$

Hence, $P_{\large\text{at least 3 with same birthday}}$

$= 1 - \left[\dfrac{365.364\ldots (365-(r-1))}{365^r}  + 365.\dfrac{364. 363 \ldots (365-(r-2))}{ 365.364^{r-2}}\right]$

$= 1 - \dfrac{365.364\ldots(365-(r-1))}{365^r}  - \dfrac{364.363 \ldots(365-(r-2))}{364^{r-2}}$

No option matches. Option C might be a typo.

Comments

Why the 364^{(r-2) ?}

---

please explain why 364^(r-2)

---

1 day is already taken by the two person having same birthday.

---

yes...so that particular day(having b'days of 2people) can be any of the 365 days....hence written in bold.....and we have remaining r-2 people and 364 days? right???   thanks Arjun Sir!!

---

In Case 2 you have written among 365 people.... shouldn't it be among 'r' people?

---

Arjun Sir, for the second case, should not it be  365^r instead of 364^r−2 ?

there are total 365^r elements in the sample space and among those C(r,2).365.364.363⋯(365−(r−2)) elements are such that exactly two people has same bday.

---

There are no answers in those options,  Infact, its a slightly complicated question. We need to consider the possibility of multiple pairs having same birthdays but on different dates  ( exactly two people having same birthday is not enough to complement having atleast one triplet)
 
Please go through

https://math.stackexchange.com/questions/1544460/group-of-r-people-at-least-three-people-have-the-same-birthday

---

Same confusion as @ Sourav Basu .

Can someone clarify??

---

@Arjun Sir,

Can you please check that link which is mentioned above having correct answer?

---

P(exactly 2 having same birthday)= C(r,2).365.364.363…(365−(r−2))/364^(r−2)

here putting r=3 i.e. among 3 persons if we are calculating the probability of 2 people having the same birthday then it comes out to be >1 in fact it is 3*365.

 

how can it be correct?

---

@sree2018 Birth year is irrelevant here. All we have to do with birthday only which are taken as $365$ here. 

---

Above explained solution is wrong .If we consider 2 out of 3 people have same bday the above solution is yielding a probability of 3*365

---

If we take $r=4$, option C gives a large negative probability. 😅

---

If r=4,

P(3) + P(4)

=>$_{3}^{4}\textrm{C} * (\frac{1}{365^3}* \frac{364}{365}) + _{4}^{4}\textrm{C} *(\frac{1}{365^4})$

=>8e-10

=> no options match.

Am i wrong? Please help.

---

sir i think above answer is totally incorrect, because while putting the value of 'r' in above question, let us suppose 3, it is giving us totally incorrect result. we are not getting the result in between 0and 1

---

Fixed the answer now.

---

Consider the following scenario: persons A and B have birthday X while persons C and D have birthday Y. This sort of situation is not accounted for if you're only counting ways there can be precisely one pair of persons sharing a birthday. It is possible for multiple pairs of persons to share birthdays without any three sharing a birthday

---

@Arjun Sir, I think $P_{exactly 2 having same birthday}$ should be multiplied by $C_{2}^{r}\textrm{}$

because we can select 2 such people in $C_{2}^{r}\textrm{}$ ways.

Please correct me if I am wrong.

Answer 2

The correct answer(which is not in the options) should be =

$1- \dfrac{365 \cdot 364 \dots (365-r+1)}{365^{r}} - ^{r}C_{2} \cdot 365 \cdot \dfrac{ 364 \cdot 363 \dots (364-(r-2)+1)}{365^{r}}$

i.e. $1 - Probability(all\: 'r' \: people \: have \: distinct\: birthdays) - Probability(only\: 2 \: people \: have \: same\: birthdays)$

Try the formula for say r=3, then the answer should be $\frac{\binom{365}{1}}{365^{3}}=\frac{1}{365^{2}}$ (which can be found directly).

Answer 3

Its answer is 3).. but instead of  '+' there would be a  '-' .

P(Atleast three have B'day on same day) = 1-  ( P(No person having B'day on same day) + P(Two persons having B'day on same day) )

Answer 4

We have r people and 365 days , so total cases are (365)^r 

P(at least 3 have same day bday)=1-P( no two have same day bday) --( exactly 2 have same day bday) - equation one

Case1: P( no two have same day bday)= all have different day bday 

So it we have 4 people we have 4 days then and all have different bdays in 4! Ways,so here we have r people we will select r days by 365 C r * r! Ways which is 365.364....(365-(r-1))/(365)^r

Case 2: exactly 2 have same day bday :-We will select 2 out of r people have treat them as single entity and they can have bday on same day and that can be any one  of 365 days,so 365 ways  i.e  rC2*365 ,we have 364 days remaining and r-2 people which have bday on diff day so similar to case 1 we have total case=(364)^r-2 and favourable will be selecting r-2 days out of 364 and we have 364 C r-2 * (r-2)! = 364*363....(364-(r-3) ) the last bolded term can be written as (365-(r-2)) 

So we get rC2* 365  *   364*363.....(365-(r-2))/(364)^r-2

Substitute both cases in equation one ,Answer will be C

Comments

Pls explain total cases 365^r?

---

For total cases:

1^st person  bday have 365 possibilities.

2^nd person bday have 365 possibilities and so on.

Upto rth person bday have 365 possibilites.

Total possibilites =

possibilites for 1^st * possibilities for 2^nd * -------------- * possibilities for rth person = $365^{r}$