A hostess is planning a party and wants to award a prize or prizes to any of the guests who have the same birthday as any other guest. How many should she invite to the party to be 50% sure that at least two guests have the same birthday?It is assumed that for all guests birthdays are independent (no twins are invited) and are randomly distributed over the days of the year, and that anyone born on February 29 celebrates his birthday on February 28.
The question states "at least two" and not "exactly two," so the problem may be approached from the standpoint of the probability that no guests have the same birthday. That is possible if the number of guests is 365 or less.
Let d be the number of possible distinct birthdays and n be the number of persons invited. Let PERM(d,n) represent the number of permutations of d different things taken n at a time. The number of ways the n people could have distinct birthdays is PERM(d,n) and the number of ways n people could have any birthday at all is d n, so that the probability that the n people all have distinct birthdays, assigning each birthday to a particular person, is
q = PERM(d,n)/dn. Either no birthdays match or some do, so that the probability that some do is p = 1 - q. p approximates 1/2 for d = 365 and n = 23. To most people a value of n = 23 for p = 1/2 is unexpectedly low, hence the paradox.Now let us inquire how many people must be invited for a 50-50 chance that at least one will share the hostess's birthday. The probability is 364/365 that any particular person will not share the hostess's birthday and is (364/365)n that none of n persons will have that birthday. Setting this equal to 1/2 and solving for n we find that
n = 252.6519888, which we would round up to 253.A more general statement of the classical birthday problem is
If n distinguishable items are picked and replaced at random from a set containing d items, how many items must be picked for the probability of picking the same item twice to exceed 50%?Now let us inquire how many persons must be invited to insure a 50% probability that exactly two guests will have the same birthday. That problem appears to be closely related to the original problem but the answer is quite different. Actually it is not possible. As the number of guests increases the probability increases until it reaches a maximum of 0.38643 for 28 guests and declines from that point onward. That is due to the increasing probability of the occurrence of three or more matching birthdays.
Specify that there are exactly m persons with the same birthday. That can be any one of d days and there are
COMB(n,m), ways of choosing a group of m persons from a population of n, so that there ared COMB(n,m), possible configurations of this group. That leavesn - m persons who cannot have this birthday or anyone else's birthday within his own group. The number of ways that it can be so isPERM(d - 1, n - m). so the number of ways the condition that exactly m persons have identical birthdays can be satisfied isd COMB(n,m) PERM(d - 1, n - m) Divide by d n to get the probability. One also may wish to consider the probability of multiple matches.
Let us now calculate the probability that among m people there are k distinct birthdays represented. This calculation has a feature in common with The Crackerjack Box Problem in that it uses the function T(m,n), which is an enumerator for the number of ways m distinguishable objects can be distributed to n distinguishable boxes such that no box is left empty. We take T(m,k) as the number of ways m people can be assigned to exactly k birthdays such that every birthday has at least one person associated with it. If d is the number of available birthdays there are COMB(d,k) ways of choosing from them a set of size k. We multiply the number of sets of size k by the number of possible assignments for each set and divide the product by dm, which is the number of ways m persons could have any birthday whatever and arrive at the probability that m persons have k distinct birthdays as
T(m,k) COMB(d,k)/dm Setting m = k reduces this result to the classical birthday problem as a special case since
T(k,k) = k! for all k and k! COMB(d,k) = PERM(d,k)With this background we now are prepared to attack a more difficult variation of the classical birthday problem
Suzy's mother is giving her a birthday party to which she has invited all of Suzy's friends, who consist of b boys and g girls. There will be a special prize if any of the boys has the same birthday as any of the girls. What are the chances that at least one prize will be awarded? The Birthday Party
The notation for the function T(m,n) is from Combinatorics: a Problem Oriented Approach by Daniel A. Marcus, The Mathematical Association of America, 1998. It is a popular text for introductory courses in combinatorics.