Colliding PIN codes

Question

A website assigns each new user a random 3-digit PIN from $000$ to $999$ , so there are $1000$ equally likely codes.

How many users must sign up before it is more likely than not that two of them were assigned the same PIN?

Accepted Answer

This is the birthday problem with 1000 "days" instead of 365. Track the probability that all assigned PINs are distinct: P(	ext{all distinct}) = \frac{1000}{1000}\cdot\frac{999}{1000}\cdots\frac{1000-n+1}{1000}. A handy approximation: the chance of no collision is roughly e^{-n(n-1)/(2\cdot 1000)}. Setting this to 	frac12 gives n(n-1) \approx 2\cdot 1000\cdot \ln 2 \approx 1386, so n \approx 37.7. Checking the exact product, at n = 38 the no-collision probability is about 0.495, just under a half, so a collision is more likely than not. The answer is 38 users. Notice the scale: with 1000 po…

Colliding PIN codes

Your answer

Discussion

Learn the concepts

Related questions