# Math Help - Combinatorics question

1. ## Combinatorics question

Can anyone help me with this problem;

Let n ≤ 2 be an integer. Given a sequence of n integers a1,
a2,...,an, show that there exist consecutive terms in the sequence whose sum
is divisible by n. That is, show that there are i and j, with 1 ≤i j n,
such that:
sij= ai + ai + 1 + · · · + aj 0 (mod n)

Thanks

Can anyone help me with this problem;

Let n ≤ 2 be an integer. Given a sequence of n integers a1,
a2,...,an, show that there exist consecutive terms in the sequence whose sum
is divisible by n. That is, show that there are i and j, with 1 ≤i j n,
such that:
sij= ai + ai + 1 + · · · + aj 0 (mod n)

Thanks
I think this question needs to be cleaned up a bit? First, it can't be $n \leq 2$, it has to be $n \geq 2$. And that $s_{ij}$ equation looks funny. Is it
$s_{ij} = 1 + ~ ... ~ a_i + 1 + ~...~ + a_j$ or something?

-Dan

3. I guess it is

4. ## Question clean up

The question is fine on my screen, perhaps a font mismatch or something is causing it to be diplayed improperly.
But yes, the second reply accurately describes the problem.

5. If we can find $
1 \leqslant j \leqslant n
$
such that $
\sum\limits_{1 \leqslant k \leqslant j} {a_k } = \dot n$
we are done

Suppose we can't find $
1 \leqslant j \leqslant n
$
such that $
\sum\limits_{1 \leqslant k \leqslant j} {a_k } = \dot n$

We have $
\sum\limits_{1 \leqslant k \leqslant j} {a_k } \equiv 1;2;3;...;n - 1\left( {\bmod n} \right)
$
with $
1 \leqslant j \leqslant n
$

Then by the pigeon hole principle there are
$j,p \in \mathbb{N}
$
such that $
\sum\limits_{1 \leqslant k \leqslant j} {a_k } \equiv \sum\limits_{1 \leqslant k \leqslant p} {a_k } \left( {\bmod n} \right),n \geqslant p > j \geqslant 1

$

Thus: $
\sum\limits_{1 \leqslant k \leqslant p} {a_k } - \sum\limits_{1 \leqslant k \leqslant j} {a_k } \equiv 0\left( {\bmod n} \right) \Rightarrow \sum\limits_{j + 1 \leqslant k \leqslant p} {a_k } \equiv 0\left( {\bmod n} \right)
$

I hope it is ok

6. (I am too lazy to read to uncode the sigma's in Paul's post but here is how I would do it).
Consider
$b_1=a_1$
$b_2=a_1+a_2$
$b_3=a_1+a_2+a_3$
....
$b_n=a_1+a_2+a_3+...+a_n$
There are $n$ such integers for $b_k$. Now if any one of these leaves remainder of $0$ then the proof is complete. Otherwise let we have $n-1$ remainder (excluding 0) among $n$ integers so two of them leave the same remainder by pigeonholing $b_i,b_j$ with $i>j$ then $b_i - b_j = a_{j+1}+...+a_i$ is divisible by n.