An Upper Bound
The argument below is adapted from an argument of Paul Halmos.
As stated above, the probability that no two birthdays coincide is
As in earlier paragraphs, interest lies in the smallest n such that p(n) > 1/2; or equivalently, the smallest n such that p(n) < 1/2.
Using the inequality 1 − x < e−x in the above expression we replace 1 − k/365 with e−k/365. This yields
Therefore, the expression above is not only an approximation, but also an upper bound of p(n). The inequality
implies p(n) < 1/2. Solving for n gives
Now, 730 ln 2 is approximately 505.997, which is barely below 506, the value of n2 − n attained when n = 23. Therefore, 23 people suffice. Solving n2 − n = 2 · 365 · ln 2 for n gives, by the way, the approximate formula of Frank H. Mathis cited above.
This derivation only shows that at most 23 people are needed to ensure a birthday match with even chance; it leaves open the possibility that, say, n = 22 could also work.
Read more about this topic: Birthday Problem
Famous quotes containing the words upper and/or bound:
“When my old wife lived, upon
This day she was both pantler, butler, cook,
Both dame and servant, welcomed all, served all,
Would sing her song and dance her turn, now here
At upper end o’the table, now i’the middle,
On his shoulder, and his, her face afire
With labor, and the thing she took to quench it
She would to each one sip.”
—William Shakespeare (1564–1616)
“The essence of the modern state is that the universal be bound up with the complete freedom of its particular members and with private well-being, that thus the interests of family and civil society must concentrate themselves on the state.... It is only when both these moments subsist in their strength that the state can be regarded as articulated and genuinely organized.”
—Georg Wilhelm Friedrich Hegel (1770–1831)