Pigeonhole: 12 numbers between 10 to 100 - 2 have a difference divisible by 11

Question

Prove that given 12 numbers between 10 to 100 - 2 have a difference divisible by 11.

I didn't understand the answer given in my lecture and thought that as usual I'd probably get a clearer answer here.

Please explain the reasoning behind every step as I'm having quite a bit of trouble with these types of problems.

Answer 1

First observe that any number when divided by 11 will leave any one of the following number as reminder-0,1,...,10 (this fact is a consequence of ``Division algorithm"). Let us make eleven different rooms numbered as 0,1,...,10, where room $r$ will contain all numbers which have reminder $r$ when divided by 11. Now try to pick any 11 numbers. If you pick any two from the same room, their difference will be divisible by 11. Now can you pick 12 numbers without picking two numbers from at least one room?

Answer 2

The limits are completely irrelevant to the answer. The upper limit could just as well be 1,000 or 10,000.

What does matter is that there are twelve numbers. Think about the remainder when you divide each of the numbers by 11. The possible remainders are 0, 1, 2 ... 10 - and there are eleven of them. If you have twelve numbers, two of the remainders must be the same - you can only have up to eleven different, because we just counted the different ones you can have (pigeonhole). Once you have two numbers with the same remainder, you ought to be able to do the last step yourself.