= Solution
The events $B\cap A_i$ are pairwise disjoint and their union is $B$. Finite additivity and the definition of <conditional probability> therefore give the <law of total probability>:
$$
P(B)=\sum_{i=1}^nP(B\cap A_i)
=\sum_{i=1}^nP(A_i)P(B\mid A_i).
$$
For the <birthday problem>, let $D$ mean that all birthdays differ. For $n\leq365$, sequential conditioning on previous distinct birthdays and <independence of random variables> give
$$
P(D)=\prod_{j=0}^{n-1}\left(1-\frac{j}{365}\right)
\leq\exp\left(-\sum_{j=0}^{n-1}\frac{j}{365}\right)
=\exp\left(-\frac{n(n-1)}{730}\right).
$$
Here each factor uses the stated bound $1-x\leq e^{-x}$. For $n\geq29$, $n(n-1)\geq812>730\log3$, so
$$
\boxed{P(\text{at least one shared birthday})=1-P(D)\geq\frac23.}
$$
For $n>365$ a match is certain by the <pigeonhole principle>. The threshold from the exponential bound is $(1+\sqrt{1+2920\log3})/2\approx28.8$, so $29$ suffices.
Back to article page
