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 $\displaystyle n \leq 2$, it has to be $\displaystyle n \geq 2$. And that $\displaystyle s_{ij}$ equation looks funny. Is it
$\displaystyle 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 $\displaystyle 1 \leqslant j \leqslant n$ such that $\displaystyle \sum\limits_{1 \leqslant k \leqslant j} {a_k } = \dot n$ we are done

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

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

Then by the pigeon hole principle there are
$\displaystyle j,p \in \mathbb{N}$ such that $\displaystyle \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: $\displaystyle \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
$\displaystyle b_1=a_1$
$\displaystyle b_2=a_1+a_2$
$\displaystyle b_3=a_1+a_2+a_3$
....
$\displaystyle b_n=a_1+a_2+a_3+...+a_n$
There are $\displaystyle n$ such integers for $\displaystyle b_k$. Now if any one of these leaves remainder of $\displaystyle 0$ then the proof is complete. Otherwise let we have $\displaystyle n-1$ remainder (excluding 0) among $\displaystyle n$ integers so two of them leave the same remainder by pigeonholing $\displaystyle b_i,b_j$ with $\displaystyle i>j$ then $\displaystyle b_i - b_j = a_{j+1}+...+a_i$ is divisible by n.