Thursday, 13 November 2014

Data Structure Problem From Cormen


How many people should be invited to a party in order to make it likely that there are two people with the same birthday? 

Ans :
 Probability reaches 100% when the number of people reaches 367 (since there are 366 possible birthdays, including Leap year). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people.

Explanation :
Idea is 1st calculate the probability of 2 person who don't share same birthday .

Find number of pair form 23 people = 
\displaystyle{\frac{23 \cdot 22}{2} = 253}
 
1st person birthday will be 1/365
The chance of 2 people having different birthdays is: 364/365
The chance of 3 people having different birthdays is: 363/365
Change of 23 people having different birthday will be 365/365 × 364/365 × 363/365 × 362/365 × ... × 343/365 =
(1/365)23 × (365 × 364 × 363 × ... × 343)
≈ 0.492703

The chance that we have a match is: 1 – 49.95% = 50.05%, or just over half! If you want to find the probability of a match for any number of people n the formula is: \displaystyle{p(n) = 1 - \left(\frac{364}{365}\right)^{C(n,2)} = 1 - \left(\frac{364}{365}\right)^{n(n-1)/2} }
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)