Combinatorics

Question

Given m integers $a_1,a_2,....,a_m$ show that there exist integers $k,s$ with $0 \leq k < s \leq m$ such that

$a_{k+1} + a_{k+2}​​​​​​ + .....+a_s$ is divisible by $m$.

Answer 1

Make m pigeons 

a₁

a₁+a₂

a₁+a₂+a₃ 

.

.

.

.

a₁+a₂+a₃+..........+a_m

Now, if m divides any of the above m numbers (pigeons) then we got our k and s such that 

a_k+1 + a_k+2 + ....... + a_s is divisible by m.

Now if none of the above m numbers (pigeons) is divisible by m then the remainders left by them after dividing by m will belong to the set {1,2,.....,m-1}

Consider the numbers 1,2,.....,m-1 as holes.

Now, we are putting a pigeon (a₁ + a₂ + .... +a_k) in the hole r if the number (a₁ + a₂ + ... + a_k) leaves remainder r when divided by m 

Since there are m pigeons and (m-1) holes so by pigeonhole principle there exist at least one hole which contain more than one pigeon.

That means there exists at least two numbers among the above m numbers which will leave the same remainder when divided by m

Let these two numbers be (a₁ + a₂ + a₃ + .... + a_k) and (a₁ + a₂ + ....+ a_s) where k<s

So, the number (a₁ + a₂ + .... + a_s) - (a₁ + a₂ + ... +a_k) = a_k+1 + a_k+2 + .... + a_s is divisible by m.

So, given m integers a₁,a₂,....,a_m  we will always get two integers k,s with 0≤k<s≤m such that

a_k+1+a_{k+2​​​​​​}+.....+a_s is divisible by m. (Proved)