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 3 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

Named alongside it

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

Approximation Birthday problem Complementary counting Convergence rate Counting argument Dirichlet The Euler–Mascheroni constant Existence proof Expectation Harmonic series Hash collision Independence

All concepts