Matpic
mathematics, in pictures
Concept

Collision

Two things landing in the same place, which is what a counting argument produces when there are more things than places. Bounding how many places there are is therefore a way of proving that two things must coincide, without saying which two.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

13 into 12. 13 items spread as evenly as 12 boxes allow. Even at their most even, some box holds 2, because 13 is more than 12 × 1.

More things than boxes

If there are more objects than containers, some container holds two. That is the entire principle, it is impossible to disagree with, and it settles questions that look nothing like it.

discrete · Pigeonhole When a shared birthday becomes likely. The chance that some pair in a group shares a birthday, against group size. It passes a half at 23 people, where the probability is 50.7%.

Twenty-three people

A room needs 253 people before someone probably shares a birthday with you. It needs 23 before two of them probably share one with each other. The gap between those numbers is the whole problem.

probability · Birthday problem Waiting for all 6 kinds. One bar per new kind: the expected number of draws needed to see a kind not yet seen, rising as fewer of them are left, and adding to 14.70 draws in total.

How long until every one turns up

Draw at random from six equally likely kinds until all six have appeared. The wait is not six draws, and it is not sixty; it is fourteen point seven, and the number is a harmonic sum wearing a hat.

probability · Expectation A year of birthdays with a seasonal swing of ±50%, peaking in September. Bars for the 365 days of a model calendar with a seasonal swing of ±50%, peaking in September, drawn as each day's excess or shortfall against an even year. A shared birthday among 23 people has chance 54.86% against 50.73% for the even year, the first group with an even chance is 22, and the calendar behaves like 324.4 equally likely days.

Any unevenness brings the match sooner

Real birthdays are not spread evenly across the year, and every such departure pushes the famous twenty-three down rather than up. The proof is one move on two days at a time, and what it leaves behind is a single number — the one ecologists use to count species.

probability · Birthday problem The walk x² + 1 modulo 101, drawn as the letter ρ. Starting at 2 and squaring and adding 1 modulo 101, the walk visits 8 values once on a tail and then runs round a cycle of 9 values for ever.

A collision that finds a factor

A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.

probability · Birthday problem

Named alongside it

The objects these essays reach for when they reach for this one.

Birthday problemComplementary countingIndependencePigeonhole principleApproximationChinese remainder theoremConvergence rateConvexityCounting argumentDirichletThe Euler–Mascheroni constantExistence proof

All concepts