How do I check if a list of numbers have the same remainders when divided by the same number

Question

I am watching a video which explains that "when you divide by the number n, there are n possible remainders: 0, 1, 2 .... , n-1".

Then, the author says that when you are given a list of numbers starting from: 9, 99, 999 and 999......999 (2010 9s), when divided by 2009, there must be 2 numbers which share the same remainder.

For smaller numbers like: 1,2,3,4,5, divided by 5, I am certain that 1 and 6 shares the same remainder 1, when divided by 5.

But how do I "proof" that for numbers starting from 9, 99, and up to 2010 (9s) - a total of two thousand and ten numbers, when divided by the number "2009", there will be 2 numbers which share the same remainder?

Answer 1

This is the pigeon-hole principle. If the $2010$ "pigeons" $9$, $99$, $999$ and so on up to $\underbrace{999\ldots 9}_{2010}$ fly into the only $2009$ "holes" $0,2,3,\ldots, 2008$ of possible remainders when dividing by $2009$, there must be (at least) one hole where (at least) two pigeons fly in.