A hostess invites b boys and g girls to a party. What is the probability that at least one of the boys will have the same birthday as at least one of the girls?There is a simple approximate solution that is valid if the number of boys and girls is small with respect to the number of available birthdays.If we compare each of the boys with all of the girls there will be a total of b·g comparisons. The probability of no match for any particular comparison is 364/365. If the comparisons are independent of each other the probability that none of the boys will match any of the girls is
q = (364/365)bg and the probability sought is 1 - q.
The comparisons are independent only if there is no duplication of birthdays amongst the boys or the girls. If b and g both are small with respect to 365 the probability of no duplication is high and the probability of any configuration involving duplicate birthdays is low, and there is but a small error in considering the comparisons to be independent. If one specifies that the numbers of boys and girls are the same and inquires how many will be needed for a 50% probability that at least one of the boys will have the same birthday as at least one of the girls, solving the above expression gives
b = g = 16, which is the same answer given by the exact solution below.For an exact solution we must allow for the possibility of duplicate birthdays within a group. We can use a result on the Birthday Paradox page to state the probability that b boys will have exactly k distinct birthdays as
D(b,k) = T(b,k) COMB(d,k)/db
We are using d to represent the number of available birthdays and COMB(m.n) is the combinatorial function. Usually we will use
d = 365. Given that there are k distinct birthdays amongst the boys, the probability that none of the girls has any of these birthdays is((d - k)/d)g There may be anywhere from one to b distinct birthdays among the boys (with an upper limit of d), so that q, the probability of no matching birthdays between the boys and the girls is the sum of the products of the above two expressions from k = 1 to b or from k = 1 to 365, whichever is less, and the probability of at least one match is
1 - q. The exact solution is computationally more difficult than the approximate solution. For one thing it is difficult to generate values of T(m,n) to order outside of a special computing environment such as a computer algebra system. Consequently one may be reduced to the use of tables of T(m,n) or to an approximation.
This appears to be a new problem and contributions by Robert Israel and Glenn C. Rhodes are gratefully acknowledged.