| Submit | All submissions | Best solutions | Back to list |
PROG0138 - Birthday paradox |
Determine the probability $p_n$ that, in a group of $n$ randomly chosen people, some of them will have the same birthday. If we assume that each day of the year (we exclude February 29) is equally probable for a birthday, the probability that none of the people in the group have the same birthday is given by $$ q_n = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \dots \cdot \frac{365-n+1}{365} $$ The probability $p_n$ is then computed as $p_n = 1-q_n$. For the probability $p_n \in \mathbb{R}$, it always applies that $0 \leq p_n \leq 1$.
Note: The above formula is only valid for $n \leq 365$. What happens if $n>365$?
Note: By the pigeonhole principle, the probability reaches 100% when the number of people reaches 366 (since there are 365 possible birthdays, excluding February 29). However, 99% probability is reached with just 57 people, and 50% probability with 23 people. This is called the birthday paradox, not because it is a paradox in the sense of leading to a logical contradiction, but because the mathematical truth contradicts naive intuition. An intuitive guess would suggest that the chance of two individuals sharing the same birthday in a group of 23 is much lower than 50%, but the birthday problem demonstrates that this is not the case.
Input
No input.
Output
For each value $n$ that is between 5 and 75 (boundaries included) and that is a multiple of five print the value $n$ itself, a single space, and then the probability $p_n$ that in a group of $n$ people at least two people have the same birthday. Use a separate line every time.
Example
5 0.0271355736998 10 0.116948177711 15 0.252901319764 ... 75 0.999719878174
Bepaal de kans $p_n$ dat in een groep van $n$ personen minstens twee personen op dezelfde dag verjaren. De kans dat geen twee personen op dezelfde dag verjaren, wordt gegeven door $$ q_n = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \dots \cdot \frac{365-n+1}{365} $$ De kans $p_n$ bekomt men dan uiteraard als $p_n = 1-q_n$. Voor de kans $p_n \in \mathbb{R}$ geldt steeds dat $0 \leq p_n \leq 1$.
Opmerking: Bovenstaande formule werkt enkel wanneer $n \leq 365$. Wat gebeurt wanneer $n>365$?
Opmerking: Dit wordt de verjaardagsparadox genoemd, omdat deze kans groter is dan wat de meeste mensen intuïtief zouden verwachten.
Invoer
Geen invoer.
Uitvoer
Schrijf voor elke waarde van $n$ tussen 5 en 75 (grenzen inbegrepen) die een vijfvoud is op een afzonderlijke regel: de waarde van $n$, één enkele spatie, en vervolgens de kans $p_n$ dat in een groep van $n$ personen minstens twee personen op dezelfde dag verjaren.
Voorbeeld
5 0.0271355736998 10 0.116948177711 15 0.252901319764 ... 75 0.999719878174
| Added by: | Peter Dawyndt |
| Date: | 2011-08-08 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | |
| Resource: | None |
RSS