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:
“You doubt we read the stars on high,
Nathless we read your fortunes true;
The stars may hide in the upper sky,
But without glass we fathom you.”
—Ralph Waldo Emerson (1803–1882)
“Successful socialism depends on the perfectibility of man. Unless all, or nearly all, men are high-minded and clear-sighted, it is bound to be a rotten failure in any but a physical sense. Even through it is altruism, socialism means materialism. You can guarantee the things of the body to every one, but you cannot guarantee the things of the spirit to every one; you can guarantee only that the opportunity to seek them shall not be denied to any one who chooses to seek them.”
—Katharine Fullerton Gerould (1879–1944)