# 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.

-

## 1 Answer

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.

-
Since there are 9 * 10 combinations and 100 numbers then I conclude that there are at least two numbers with the same first and fifth digit. Is it correct that there are up to ten numbers with the same first and fifth digit? –  blutuu Nov 30 '12 at 8:48
@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
To clarify, does this show that there absolutely has to be at least 2 numbers with the same 1st/5th digit no matter how the numbers are distributed? I mean since there are only 90 "unique" numbers out of 100. –  blutuu Nov 30 '12 at 8:58
@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
Understood. Thanks for the help. –  blutuu Nov 30 '12 at 9:03