TIFR CSE 2022 | Part A | Question: 2

Question

We would like to invite a minimum number $n$ of people (their birthdays are independent of each other) to a party such that the expected number of pairs of people that share the same birthday is at least $1.$ What should $n$ be?

(Ignore leap years, so there are only $365$ possible birthdays. Assume that birthdays fall with equal probability on each of the $365$ days of the year.)

• A. $23$
• B. $28$
• C. $92$
• D. $183$
• E. $366$

Comments

Why the concept of expectation is used and not the pigeonhole principle here@GO Classes

Answer 1

$P\, (\text{any pair share same birthday})$ = $365*(\frac{1}{365^2})$

$E[(a,b)]=\begin{cases} 1 & \text{ if a and b share same birthday}\\ 0& \text{ otherwise } \end{cases}$

$\text{There are}\;\binom{n}{2}\; \text{pairs in total.}$

$\text{Now, according to the question}\;\; \frac{n(n-1)}{2}*\frac{365}{365^2}\geq 1$

$\text{So, minimum value of}\; n\; \text{would be 28. (because, }28*27 = 756>730\text{)}$

$\text{So, the answer is option }\textbf{B}\;.$

Answer 2

The probability person B shares person A's birthday is 1/N, where N is the number of equally possible birthdays,

so the probability B does not share person A's birthday is (1−1/N),

so the probability n−1 other people do not share AA's birthday is (1− 1/N)^n−1,

so the expected number of people who do not have others sharing their birthday is

n(1− 1/N)^n−1,

so the expected number of people who share birthdays with somebody is n(1−(1−1/N)^n−1).