# Thread: application of pigeonhole principle

1. ## application of pigeonhole principle

It is given 13 integers $\displaystyle 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 $\displaystyle 0<i<j<=13$ such that
$\displaystyle c_{i+1}+c_{i+2}+...+c_j$ is divisible by 13
for example, $\displaystyle c_4+c_5+c_6+c_7$ is divisible by 13.
(Hint:consider the following 13 integers
$\displaystyle n_1=c_1$
$\displaystyle n_2=c_1+c_2$
.
.
.
$\displaystyle 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 $\displaystyle 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 $\displaystyle 0<i<j<=13$ such that
[CENTER]$\displaystyle c_{i+1}+c_{i+2}+...+c_j$ is divisible by 13
[LEFT]for example, $\displaystyle 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 $\displaystyle n_k$ when divided by 13 are the the pigeonholes. The $\displaystyle n_k$ are the pigeons.

5. ## Re: application of pigeonhole principle

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

6. ## Re: application of pigeonhole principle

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

7. ## Re: application of pigeonhole principle

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