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

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.

-
Have you observed that any number when divided by 11 will leave any one of the following number as reminder-0,1,...,10? –  Tapu Jan 8 '12 at 17:27
Yes, for instance it's fairly straightforward when the numbers are contiguous, but when they're not contiguous I'm not sure why having 2 numbers with the same remainder is helpful. For instance there are $\binom{12}{2}=66$ possible pairs of numbers - how does having two pairs with the same remainder help me? –  Robert S. Barnes Jan 8 '12 at 17:35
@Robert: Think. What does having a difference divisible by $11$ have to do with remainders modulo $11$? –  Marc van Leeuwen Jan 8 '12 at 18:05
add comment

## 2 Answers

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?

-
Arg, so first I'm doing the division on the given numbers to sort them into the 11 "remainder" cells and then any two which have the same remainder must have a difference divisible by 11! My problem was I was trying to take the group of differences and then apply pigeonhole to it... –  Robert S. Barnes Jan 8 '12 at 17:50
See your problem was to pick 12 numbers and then check their differences and I show you that you can pick at most 11 numbers such that their pairwise differences will not be divisible by 11. But then there will be no room for your 12th number. BTW, the number 11 and 12 have nothing to do, as well. If you pick any $n$ numbers, the difference between at least one pair should be divisible by $n-1$. May be to feel what is going on, its better to understand the small $n$ cases. I recommend you try the $n=3$ case first. –  Tapu Jan 8 '12 at 18:42
add comment

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.

-
The pigeonholes in this case are the residue classes mod 11 (remainders on dividing by 11). Applying the pigeonhole principle is often about choosing the right pigeonholes. One clue is that you were given twelve objects - so you might well be looking for eleven pigeonholes. –  Mark Bennet Jan 8 '12 at 17:29
But there are $\binom{12}{2}=66$ possible pairs of differences... So since there are only 11 possible remainders, 10 if I assume none of the pairs is divisible by 11, then I want to get to a contradiction showing that if 2 pairs have the same remainder then there must be a third pair whose diff is divisible by 11? That's the part I don't get in this and other similar problems... –  Robert S. Barnes Jan 8 '12 at 17:42
@RobertS.Barnes: The number of pairs is a distraction - the pigeonhole principle enables you to pick out a particular pair - two items in the same pigeonhole - without having to analyse all the pairs. You need two numbers (one specific pair), not two pairs or three. The pigeonhole principle is a different way of searching for the pair you need - if you like it proves the existence of the pair you need without telling you which pair it is. –  Mark Bennet Jan 8 '12 at 18:58
add comment