Birthday is no problem

[wolle]

(a) Give a formula for the probability P (n) that of n randomly selected persons, at least two have their birthday on the same day. Also indicate the derivation of your solution or justify its correctness. You can assume that each year has 365 days (none of them have their birthday on February 29th) and that birthdays are evenly distributed (there are no special events that lead to higher birth rates on certain days).
(b) Determine the values ​​P (10), P (23), P (35) and P (50) to a minimum of 3 decimal places.
(c) What did you calculate in this task related to hashing?

----------

The above question was recently posted at this forum in a thread that got locked. It's obviously homework but may still be of general interest in an algorithms & data structures forum. It must be clear to the problem constructors that this problem both is quite hard and also a well-known standard problem known as the Birthday problem which even has a Wikipedia entry. It's naive to think that data structure students would bother with a difficult probability problem when it's so much easier to just Google the solution and get over with it.

On the other hand, if the Birthday problem is attacked from a hashing viewpoint it becomes much simpler, even easy. The hashing point of view offers an effective solution strategy. Instead of solving the Birthday problem first and then figure out what it has to do with hashing it would be more meaningful if the exercise were posed the other way around like this:

Use your knowledge of hashing and the hints below to solve the Birthday problem and code it in your language of choice. You get points for ingenuity of solution, cleverness of conclusions and elegance of code:

1. Imagine a row of 365 empty chairs.

2. Repeatedly select a chair with probability 1/365 and place a person in it.

3. There exists a function based on date-of-birth that maps any person onto a number between 1 and 365.

4. Someone who gets assigned a free chair is considered lucky.

5. At first all chairs are free so the first person will be lucky with probability 1. As the chairs fill up the probability of luck gets smaller to finally become 0 when all chairs are occupied.

6. The probability that exactly the k'th person is lucky depends solely on the number of remaining free chairs in relation to the total number of chairs.

7. The combined probability that all of k persons are lucky is the product of the luck probability of each of the k persons.

8. The probability that at least one of k persons is unlucky is the complement to the probability that all k persons are lucky.

[MortenComp]

Never heard about such problem. But as it turned out, this paradox is indeed described in Wikipedia. The topic is quite interesting and not simple. I think about it all evening ....