# Thread: application of pigeonhole principle

1. ## application of pigeonhole principle

It is given 13 integers $c_1,c_2,...,c_{13}$ (some of them may be the same). Use pigeonhole principle to prove that there exist i and j with $0 such that
$c_{i+1}+c_{i+2}+...+c_j$ is divisible by 13
for example, $c_4+c_5+c_6+c_7$ is divisible by 13.
(Hint:consider the following 13 integers
$n_1=c_1$
$n_2=c_1+c_2$
.
.
.
$n_{13}=c_1+c_2+...+c_{13}$
and their remainder when divided by 13)

2. ## Re: application of pigeonhole principle

Originally Posted by maoro
It is given 13 integers $c_1,c_2,...,c_{13}$ (some of them may be the same). Use pigeonhole principle to prove that there exist i and j with $0 such that
[CENTER] $c_{i+1}+c_{i+2}+...+c_j$ is divisible by 13
[LEFT]for example, $c_4+c_5+c_6+c_7$ 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.

3. ## Re: application of pigeonhole principle

But how this question is related to the pigeonhole principle?

4. ## Re: application of 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 $n_k$ when divided by 13 are the the pigeonholes. The $n_k$ are the pigeons.

5. ## Re: application of pigeonhole principle

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

6. ## Re: application of pigeonhole principle

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

7. ## Re: application of pigeonhole principle

Originally Posted by maoro
But how about if all of $n_i$ is not divisible by 13?
That means the zero pigeonhole some $n_j$ so it is divisible by 13.