How many people should there be in a group so that the probability of at least two of them having the same birthday (that is, they were born in the same month and on the same day) is at least 50 per cent?

Perhaps an immediate guess would be half the number (365) of days in a year. However, the answer is well below this. Many would be surprised that the 50 per cent probability is attained if the group has at least 23 members. This is known as the Birthday Paradox. This result is based on the assumption that all birthdays are equally likely.

Let us confirm this. Thus, let n be the number of people. To keep calculations simple, we shall assume nobody was born on February 29, or rather, that leap years do not exist. If n is larger than 365, then clearly there must be two same birthdays (why?). This follows by the pigeonhole principle.

Suppose n is at most 365. Let us order the n people and record their birthdays in a list according to this order. The number t of possibilities of having two same birthdays is the total number N of possible birthday lists (each with n birthdays) minus the number d of those in which the birthdays are all different. The probability p of having two same birthdays is t divided by N. Since t=N-d, we have p=(N-d)/N. Elementary counting results tell us that N is 365 to the power of n (the multiplication of n 365s) and d is 365 x 364 x 363 x ... x (365-n+1).

Having a complete formula for p in terms of n, we can verify that p is at least 50 per cent if, and only if, n is 23 or larger.