\problemdata      
        {?} % latex-friendly label for the prob.
        {Pigeonhole} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, PS8} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
{\bf The Pig Principle}

Having reached $(n,n)$ successfully but having been pooped on by a pigeon
along the way, Theory Pig now has a new beef.  He complains that the name
``Pigeonhole Principle'' is verbose and awkward and proposes the following
``Pig Principle'' that he finds much more relevant to his life:

Suppose that $m$ pigs are lined up, and each pig is given some number of
tasty treats.  Theory Pig asserts that there is always a sequence of one
or more consecutive pigs in the lineup who receive a total number of
treats which is a multiple of $m$.

For example, suppose there are $m = 5$ pigs, and that they
receive 1, 6, 2, 12, and 7 treats respectively.  Then the claim holds
in this case, because the second, third, and fourth pigs received $6 +
2 + 12 = 20$ treats altogether, and 20 is a multiple of 5.

Prove that Theory Pig's Pig Principle is correct.  In the process, you may
have to use the Pigeonhole Principle one last time.  \iffalse (Optionally,
you may want to think about whether the two principles are actually
equivalent, or whether Theory Pig has just proposed a weaker principle to
replace the Pigeonhole Principle.)\fi

\solution{Let $t_i$ be the total number of treats given out to the first
$i$ pigs in the lineup.  There are two cases.

In the first case, suppose that at least one of $t_1, t_2, \ldots, t_m$ is
congruent to 0 modulo $m$.  In particular, suppose that $t_j$ is congruent
to 0 modulo $m$.  This implies that the number of treats received by the
first $j$ pigs is a multiple of $m$, and so the claim holds.

In the second case, suppose that none of $t_1, t_2, \ldots, t_m$ is
congruent to 0 modulo $m$.  Then each of the $m$ terms $t_1, t_2, \ldots,
t_m$ is congruent to one of the $m-1$ values $1, 2, \ldots, m-1$ modulo
$m$.  By the Pigeonhole Principle, there are at least two terms $t_j$ and $t_k$
that are congruent to the same value modulo $m$.  Thus pigs $j+1, j+2,
\ldots, k$ received a total of $t_k - t_j$ treats, which is a multiple of
$m$.}

\end{problem}