Pigeon-Hole Principle?

Question

Show, with the aid of the Pigeon-hole principle, that given any eleven integers, there must exist two of them whose difference is of magnitude which is a multiple of 10.

Can anyone pls help? Thanks!

Answer 1

The previous answers have the right idea, but not the right precision. How do we know that this will work for any 10 integers?

There's something called modulo arithmetic. Basically, it counts by whatever you're modding by (so mod 3 means you count 0,1,2,0,1,2...).

The nice thing about this, is in mod X, if Y=NmodX (Y is equivalent to N modX), you know that the difference between Y and N is a multiple of X.

Let's look at your case. We want to be looking in mod(10). There are ten possibilities for any one integer to be, mod 10. They are 0,1,2,3,4,5,6,7,8, and 9.

Now we want to put eleven things into this set uniquely. It can't be done. You can't put 11 pigeons into 10 holes and have 1 per hole.

So two of the integers must be equivalent mod 10. This means that their difference is a multiple of 10.

Tada!

Answer 2

Partition the integers into 10 sets, those that are multiples of 10, those that are 1 more than a multiple of 10, and so on up to those that are 9 more than a multiple of 10. [the numbers in each equivalence class are congruent modulo 10]. So the second set contains 1, 11, 21, and so on, and the differences between them are (naturally) multiples of 10.

So to use your Pigeon-hole principle, you can put 10 of your 11 integers into distinct equivalence classes, but the 11th will have to go into a class that already contains 1 of the first 10, and those 2 will differ by a multiple of 10.

Answer 3

Very tricky but I think that I have it. There are only 10 digits possible for the units digit. The differences of 11 integers must yield at least one zero, that is, a multiple of 10.

Answer 4

hi
for example take integers 1,2,3,4,5,6,7,8,9,10 we need one more that is the eleventh one. irrespective of what the 11th integer is going to be the units digit has to be one among 0,1,2,3,4,5,6,7,8,9 ; in which case the difference between this 11th integer and one other will always be multiple of 10.