\problemdata                                                             
        {sums} % latex-friendly label for the prob.
        {pigeon-hole principle} % The topic(s) of the problem content.  
        {Proof from the book} % Source (if known)                                          
        {S01 Tutorial 7, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Suppose we are given $n$ integers $a_1,
\ldots,a_n$, which need not be distinct. Then there is always a set of
consecutive numbers $a_{k+1},a_{k+2},\ldots,a_l$ whose sum $\sum_{i=k+1}^l
 a_i$ is a multiple of $n$.

\solution{
Consider the set $N$ of size $n+1$ of the partial sums of the $a_i$,
starting from the left:
$\{0,a_1,a_1+a_2,\ldots,a_1+a_2+\ldots+a_n\}$. The elements of this
set are the ``pigeons'' and $p\in N$ is placed in the hole $p\bmod
n$. There are $n$ holes $R=\{0,1,\ldots,n-1\}$. Since there are $n+1$
elements of $N$ and only $n$ elements of $R$, there must be two
distinct elements $a_k$ and $a_l$ ($k<l$ without loss of generality) of 
$N$ which map to the same element of $R$, that
is,

$$
\sum_{i=1}^l a_i \bmod n=\sum_{i=1}^k a_i \bmod n
$$

Subtracting, we see that

$$\left(\sum_{i=1}^l a_i-\sum_{i=1}^k a_i\right)=\sum_{i=k+1}^l a_i$$

is divisible by $n$.
}
\end{problem}
                                 