Thread: application of pigeonhole principle

It is given 13 integers (some of them may be the same). Use pigeonhole principle to prove that there exist i and j with such that

is divisible by 13

for example, is divisible by 13.
(Hint:consider the following 13 integers

.
.
.

and their remainder when divided by 13)

Originally Posted by maoro

It is given 13 integers (some of them may be the same). Use pigeonhole principle to prove that there exist i and j with such that
[CENTER] is divisible by 13
[LEFT]for example, is divisible by 13.
(Hint:consider the following 13 integers

The idea behind this proof is that if two numbers have the same remainder when divided by 13 then there difference is divisible by 13.

But how this question is related to the pigeonhole principle?

Originally Posted by maoro

But how this question is related to the pigeonhole principle?

Of course, we use the pigeonhole principle.
The reminders of the of the when divided by 13 are the the pigeonholes. The are the pigeons.

I got you mean.
Suppose is 14,then its remainder is 1 when is divided by 13
there is one pigeonhole containing more than 1 pigeon.

But how about if all of is not divisible by 13?

Originally Posted by maoro

But how about if all of is not divisible by 13?

That means the zero pigeonhole some so it is divisible by 13.