# Thread: Pigeonhole and SS numbers

1. ## Pigeonhole and SS numbers

Two social security numbers "match zeros" if a digit of one number is zero iff the corresponding digit of the other is zero.

Ex. 120-90-1109
430-20-5402

these numbers match zeros.

Prove: Given 513 SS numbers, there must be at least two that match zeros.

2. A 9-bit string is a string of length 9 made of 0’s & 1’s.
There are $2^9 =512$ different 9-bit strings.
If we have a collection of 513 9-bit strings then at least two are equal.
Now think of a SS#, change all the nonzero digits to 1’s.
EX: 120-90-1109 becomes 110101101 & 430-20-5402 becomes 110101101.
That is one 9-bit string. Can you finish?

3. That's a good way to look at it!

Then by the pigeonhole principle, an axiom that we must believe to hold true, we can conclude that : if we have 513 strings , and only 512 possible strings, then two or more of the strings must be identical (in terms of 0's).
More precisely, - two of the strings "match zeros"

Awesome!