2
$\begingroup$

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.

  • 0
    @Robert: Think. What does having a difference divisible by $11$ have to do with remainders modulo $11$?2012-01-08

2 Answers 2

3

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?

  • 0
    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.2012-01-08
5

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.

  • 1
    @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.2012-01-08