The crowded room

A classroom has 30 students. What's the probability that two of them share a birthday?

What do you think?

With 365 possible birthdays and only 30 people, what's the probability two share a birthday?

Drag the slider to see how quickly the probability climbs.

Birthday Pair Web

Birthday Collision

365 possible birthdays. Do any two people share one?

People in room: 23

23060

51%

chance two people share a birthday

CollisionNo collision

51%

49%

23 people = 253 pairs to compare (50% threshold)

Try it yourself. Add students to a classroom and watch for the first birthday match:

Birthday Paradox

Students

Pairs

-0

P(match)

Run many trials to see the empirical frequency converge to theory:

Birthday Batch Simulator

Class size: 23

22380

Trials

Empirical P

Theoretical P

50.7%

At just 23 people, you hit 50%. By 30 people, it's over 70%. By 50 people, it's nearly certain.

Why your intuition fails

You might reason: "With 365 days, I need about half (maybe 183 people) for a 50% chance." But that answers the wrong question.

What do you think?

That reasoning answers which question?

With 23 people, you're not checking 23 possibilities. You're checking $\binom{23}{2} = 253$ pairs. That's 253 chances for a match.

The number of pairs grows much faster than the number of people. Doubling the people quadruples the pairs.

Add people to a room and watch the number of pairs explode:

Pair Counter

People

Pairs

Pairs = n(n-1)/2 = 1×0/2 = 0

See the mesh of connections grow:

Pair Network

People in room: 4

210

People

Pairs

Double the people → 4× the pairs

How many pairs are there with 10 people? (whole number)

1/2

The math: counting "no collision"

Rather than calculate every way two people could match, flip the question: what's the probability nobody shares a birthday?

Calculating P(no collision)

P(\text{person 1 unique}) = \frac{365}{365}

Person 1 can have any birthday. No conflict possible yet.

Step 1 of 5

The square root law

The collision threshold follows a simple pattern:

Square Root Rule for Collisions

For $N$ possible values (buckets, birthdays, hash outputs), you need roughly $\sqrt{N}$ items for a 50% collision probability.

$k \approx 1.177\sqrt{N}$

For 365 days: $1.177 \times \sqrt{365} \approx 23$ people.

A hash produces 10,000 possible values. Roughly how many items for 50% collision? (whole number)

This is called the birthday attack in cryptography, and it's why security assumptions often fail.

Why this breaks security

Consider a 32-bit hash function. It has $2^{32} \approx 4.3$ billion possible outputs. Sounds safe?

What do you think?

How many items would you need for a 50% collision chance with 4.3 billion possible outputs?

Collision thresholds by system

System	Possible Values	50% Collision At
Birthdays	365	23 people
16-bit hash	65,536	302 items
32-bit hash	4.3 billion	77,000 items
64-bit hash	2⁶⁴	~5 billion items

Pick a system or enter a custom hash size to see how many items produce a collision at any probability:

Collision Calculator

365 days possible values

Target collision probability: 50%

1%50%99%

items needed for 50% collision chance

k (items)

√N

k/√N = 1.204

This is why MD5 (128-bit) is broken for security. Attackers need "only" $2^{64}$ attempts to find a collision, which is computationally feasible with enough resources.

Modern cryptographic hashes use 256 bits or more. With $2^{256}$ buckets, you'd need $\approx 2^{128}$ items for a 50% collision. That's beyond any conceivable computation.

The general formula

For a target collision probability $p$ :

General Collision Formula

$k \approx \Large\sqrt{2N \cdot \ln\left(\frac{1}{1-p}\right)}$

For $p = 0.5$ : $k \approx 1.177\sqrt{N}$

For $p = 0.99$ : $k \approx 3.03\sqrt{N}$

Even for near-certain collisions, you only need about $3\sqrt{N}$ items. The square root dominates.

For N = 1,000,000 and p = 0.5, approximately how many items are needed? (whole number)

The deeper pattern

The birthday paradox is really about pairs.

When you have $n$ items, you have $\binom{n}{2} = \frac{n(n-1)}{2}$ pairs. That grows as $n^2$ , not $n$ .

This quadratic growth explains why "unlikely" collisions happen so quickly. You're getting $n^2/2$ chances for a match, not just $n$ .

Any time you ask "do two things match?", you're counting pairs. And pairs grow quadratically.

Watch the race between people and pairs. Drag the slider and see quadratic growth in action:

People vs. Pairs

People (n): 5

13060

People (n)5

Pairs C(n,2)10

People

Pairs

Ratio

2.0×

C(5, 2) = 5 × 4 / 2 = 10

Test your understanding

In a room of 50 people, how many pairs exist? (whole number)

A system has 1 million possible IDs. Roughly how many users before 50% collision chance? (whole number)

True or False: With 100 people in a room, it's nearly certain two share a birthday.

A 128-bit hash needs 2^64 items for 50% collision. A 256-bit hash needs 2^___ items. (whole number)