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

This is harder problem based on "Birthday paradox"

Can we think like If i am not wrong :

$$P(\text{at least 3 share}) = 1 - P(\text{no 3 share})$$

The event "no 3 share" means that for every day of the year, there are at most two people born on that day. they cover two possibility

Everyone has a unique birthday (no two people share).

Exactly one pair shares a birthday, and everyone else has a unique birthday.

We know no two people share birthday we can calculate easily ..that's not big deal

Let's calculate "pair share a birthday"

Choose the pair of people who share the same birthday: $\binom{r}{2}$ ways.

Choose the day that they share: $365$ ways.

For the remaining $r-2$ people, choose $r-2$ distinct birthdays from the remaining $364$ days: $P(364, r-2)$ ways.

Total ways for "pair share a birthday" = $\binom{r}{2} \times 365 \times [364 \times 363 \times \dots \times (364 - (r-2) + 1)]$

That means "atmost two people share their birthday" = $$\left[ \frac{365 \cdot 364 \dots (365 - r + 1)}{365^r} + \binom{r}{2} \cdot 365 \cdot \frac{364 \cdot 363 \dots (364 - r + 3)}{365^r} \right]$$

 

---

 

Credit : @P0535_Yedidyah_Sagar (More simplified answer for this given solution)

Note: Before going to this solution first solve this beautiful problem : 

https://gateoverflow.in/206019/birthday-paradox?show=206019#q206019 

Important : We calculate the complement—the probability that no birthday occurs 3 or more times.If no birthday occurs 3+ times, then every birthday appears either 0, 1, or 2 times.

Let \( k \) be the number of birthdays that are shared by exactly 2 people.

Since each such birthday takes 2 people, the total people in these pairs is \( 2k \).

The remaining \( r - 2k \) people must all have unique birthdays.

The possible values of \( k \) are \( 0, 1, 2, \dots, \lfloor r/2 \rfloor \).

Now, count the number of favorable birthday assignments for a fixed \( k \):

Choose which \( k \) birthdays will be the "pair" days:

\[

\binom{365}{k}

\]

Choose the \( r-2k \) unique birthdays from the remaining \( 365 - k \) days:

\[

\binom{365-k}{r-2k}

\]

Assign the \( r \) distinct people to these chosen days.

Use Multinomial coefficient : https://en.wikipedia.org/wiki/Multinomial_theorem

 

We have \( k \) pairs, meaning \( k \) groups of 2 identical slots.The number of ways to partition \( r \) labeled people into these groups is the multinomial coefficient:

\[

\frac{r!}{(2!)^k (1!)^{r-2k}} = \frac{r!}{2^k}

\]

Multiplying these together gives the number of arrangements for a specific \( k \):

\[

\text{Count}(k) = \binom{365}{k} \binom{365-k}{r-2k} \frac{r!}{2^k}

\]

To get the total number of outcomes where nobody shares a birthday 3+ times, we sum this over all valid \( k \):

\[

\text{Total Complement} = \sum_{k=0}^{\lfloor r/2 \rfloor}

\binom{365}{k} \binom{365-k}{r-2k} \frac{r!}{2^k}

\]

The total possible birthday assignments without restrictions is:

\[

365^r

\]

 the probability of the complement is:

\[

P(\text{no 3+ match}) = \frac{1}{365^r}

\sum_{k=0}^{\lfloor r/2 \rfloor}

\binom{365}{k} \binom{365-k}{r-2k} \frac{r!}{2^k}

\]

 Using the complement rule:

\[

\boxed{P(\text{at least 3 share a birthday}) = 1 - \frac{1}{365^r}

\sum_{k=0}^{\lfloor r/2 \rfloor}

\binom{365}{k} \binom{365-k}{r-2k} \frac{r!}{2^k}}

\]

---

Many Birthday Paradox problem : https://gateoverflow.in/search?q=birthday%20paradox&start=0

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).

Comments

I think this is Wrong, because after subtraction from 1, your answer include the cases where we can have pairs which share birthday i.e A,B can have birthday on 10th Feb and C,D can have birthday on 25th Feb. Now probability for this case is included in your answer . But question specifically asked for atleast 3

---

what u are saying is that maybe 2 pairs share same bdays but we subtracted the case where no 2 bdays coincide and no one has bdays on diff dates so i think ans is right

---

I think @Hania3006 is correct.

Once go through this link : Triple Birthday Problem

Now I think, the options are beyond repairable. 

---

hey bro thamx alot thats an amzing pdf. I was terribly wrong.

beautiful pdf and ans really everyone should see this, ill encourage u to write the correct answer since none are correct here

---

Sure bro, I will try to answer it.

---

HI @Bruh
Sorry for the delay. I have added my answer. Please go through it. 
And if possible, please give any feedback to imporve the answer

Link : Answer

Answer 3

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

Answer 4

 

Please Refer : Triple Birthday Problem

Comments

yup thats a perfect sol thanx for clearing

---

Your answer is correct brother !!

Answer 5

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 6

Probability of 3 or more people having birthday on same day = 1 – (probability of 2 people having birthday on same day + probability of all having distinct birthdays)

All possible ways to choose a birthday for r people = 365*365*… (r times) = $365^{r}$

Case 1: All have distinct birthdays.

No of ways = $^{365}P_{r}$.

Probability = $\frac{^{365}P_{r}}{365^{r}}$
 

Case 2: Among 365 people If exactly 2 persons have birthdays on same day.

Then we can consider these 2 people as a unit.

Ways to choose 2 people out of r people = $^{r}C_{2}$

Then the birthday for the unit of these two people can be chosen in 365  ways.

For the remaining r-2 people, we can choose distinct birthdays out of the remaining 364 days in $^{364}P_{r-2}$ ways.

Probability = $\frac{^{r}C_{2} * 365 * ^{364}P_{r-2}}{365^{r}}$
 

Hence, Probability of 3 or more people having birthday on same day

= 1 – ( $\frac{^{365}P_{r}}{365^{r}}$ + $\frac{^{r}C_{2} * 365 * ^{364}P_{r-2}}{365^{r}}$ )

You can try out the above formula with r=3. The expected answer is $\frac{1}{365^{2}}$

No option matches this. Option C may be a typo.