0

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?

ilovetolearn
  • 1,341

1 Answers1

5

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.

Hagen von Eitzen
  • 374,180
  • 1
    I heard alternative story - if you drill 2010 holes (labeled $9$, $99$, $9\ldots9$) in 2009 pigeons ($0, 1, \ldots, 2008$), then there is at least one pigeon with two holes in it. – enedil Mar 02 '19 at 14:41
  • but that's on the assumption that each number has a unique remainder. – ilovetolearn Mar 02 '19 at 14:58
  • if there were more than 2 numbers which share the same remainder, then this assumption wouldn't hold. – ilovetolearn Mar 02 '19 at 14:59
  • but how do I proof that each number has a unique remainder, thus the two thousand and tenth number, would definitely share a remainder with another number, fulfilling the pigeon hole principle. – ilovetolearn Mar 03 '19 at 02:55