# pigeonhole principle and division

How is it possible to prove with the use of the pigeonhole principle that in every set of 2012 different numbers that are bigger or equal to zero there is at least one subset that if you sum up its elements you get a number is a multiple of 2012.

Ron .g.

-

Let $x_,x_2,...,x_{2012}$ be the 2012 integers. Consider the integers: $$x_1$$ $$x_1+x_2$$ $$x_1+x_2+x_3$$ $$.$$ $$.$$ $$.$$ $$x_1+x_2+...+x_{2012}$$ If one of these numbers is equivalent to $0$ mod 2012, then we re done. Otherwise , we find that two of these numbers must have the same remainder when divided by 2012.This is because these are 2012 numbers whose remainders when divided by 2012 form a subset of {1,2,...,2011} Let $x_1+...+x_i=x_1+x_2+...+x_j$ (mod 2012) (where $i<j$). Now we find that $\sum_{n=i+1}^{j} x_n=0$ (mod 2012), and this is the required subset.
MORE GENERAL. Prove in every set of $n$ different numbers that are bigger or equal to zero there is at least one subset that if you sum up its elements you get a number is a multiple of $n$.
Proof. Let $a_1,a_2, \cdots, a_n$ be the $n$ integers. Consider $n$ sums: $$S_1=a_1, S_2=a_1+a_2, S_3=a_1+a_2+a_3, \cdots, S_n=a_1+a_2+ \cdots a_n$$ Case 1. If in this $n$ sums, there is at least one sums is divisible by $n$. Q.E.D.
Case 2. If in this $n$ sums, there is no sums which is divisible by $n$. Hence, by Pigeonhole principle, there is exist $2$ sums $S_i,S_j \; (1 \le i<j \le n)$ such that $n|S_j-S_i$ or $n|a_{i+1}+a_{i+2}+ \cdots+ a_j$. We have Q.E.D.