# application of pigeonhole principle

• Nov 30th 2011, 07:41 PM
maoro
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)
• Dec 1st 2011, 03:03 AM
Plato
Re: application of pigeonhole principle
Quote:

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.
• Dec 1st 2011, 03:46 AM
maoro
Re: application of pigeonhole principle
But how this question is related to the pigeonhole principle?
• Dec 1st 2011, 04:11 AM
Plato
Re: application of pigeonhole principle
Quote:

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.
• Dec 1st 2011, 04:58 AM
maoro
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.
• Dec 1st 2011, 06:00 AM
maoro
Re: application of pigeonhole principle
But how about if all of $n_i$ is not divisible by 13?
• Dec 1st 2011, 06:05 AM
Plato
Re: application of pigeonhole principle
Quote:

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.