# Pigeon Hole Problem

Prove that of any 100 different twelve digit numbers (first digit cannot be zero) there are two of them with the same first and fifth digit.

I'm new to this principle and need some assistance. I've been trying to understand how to approach this problem, but no dice. I guess I understand that there are two "pigeons" in the same "box", but still need help going through this.

-

HINT: There are $9$ possible first digits, $1,2,\dots,9$, and $10$ possible fifth digits, $0,1,2,\dots,9$, so there are $9\cdot10$ possible combinations of first and fifth digits. If you have more than $9\cdot10$ twelve-digit numbers, ...
In other words, the pigeons are the $100$ numbers, and the boxes are the $9\cdot10$ possible combinations of first and fifth digit.
@blutuu: You can’t really say much about how the extras are distributed. It’s possible, after all, that all $100$ numbers have the same combination of first and fifth digits! At the other extreme, it’s possible that there are $10$ combinations that are represented twice, the other $80$ being represented once each. Or you might have $89$ combinations represented once each and the $90$-th represented $11$ times, or any of many, many other possibilities. – Brian M. Scott Nov 30 '12 at 8:51
@blutuu: Yes, it does. Imagine sorting your $100$ numbers into boxes according to their combination of first and fifth digits. There are only $90$ different boxes, so the moment you have sort the $91$-st number, you absolutely must have at least two numbers in one box: there simply aren’t $91$ different boxes. – Brian M. Scott Nov 30 '12 at 9:00