Birthday paradox

The birthday paradox states that if there are 23 people in a room then there is a chance of more than 50% that at least two of them will have the same birthday. This means that in a typically-sized school class, where the 'paradox' is often cited, an even higher probability often applies. For 60 or more people, the probability is already greater than 99%. This is not a paradox in the sense of leading to a logical contradiction; it is a paradox in the sense that it is a mathematical truth that contradicts common intuition. Most people estimate that the chance is much lower than 50:50. Calculating this probability (and related ones) is the birthday problem. The mathematics behind it has been used to devise a well-known cryptographic attack named the birthday attack.

Near matches

Another generalization is to ask how many people are needed in order to have a better than 50% chance that two people have a birthday within one day of each other, or within two, three, etc., days of each other. This is a more difficult problem and requires use of the inclusion-exclusion principle. The results (assuming an equal distribution for birthdays) are just as surprising as in the standard birthday problem:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Thus in a family with six members, it is more likely than not that two members will have a birthday within a week of each other.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~