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

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