A problem on pigeonhole principle Following is a problem, which makes use of the pigeonhole principle. But How?
"Let $A$ be a set of $n$ integers. Prove that $A$ contains a subset such that
the sum of its elements is divisible by $n$."
I found some solutions which say there are going to be $n+1$ pigeons (for partial sums) and $n$ holes (For remainders). But, are the partial sums not going to be $2^{n}-1$? (Excluding the empty subset).
 A: If you find two arbitrary subsets with the same remainder on division by $n$, how do you build from that a subset which has remainder zero? You don't need that many subsets, but you do need them to be related to each other. We allow the remainders $1, 2 \dots n-1$, because if we have remainder zero we are done.  There are $n-1$ pigeonholes.
Then take $a_1; a_1+a_2,; a_1+a_2+a_3; \dots ; a_1+a_2+\dots a_n$. We have $n$ sums there, so two of them must be equal. Now what happens when you take the difference, which doesn't happen in the case of general unrelated subsets?

I was avoiding taking the empty sum - zero - as one of my sums, but that can be included with $n$ pigeonholes including remainder zero, and $n+1$ sums. Personally, I think what I did is clearer, but others may disagree.
A: Let $A=\{a_1,\cdots,a_n\}$ where none of the $a_i$ is zero. 
Consider the $n+1$ numbers:
$b_0=0,\\ b_1=a_1, \\ b_2=a_1+a_2, \\ b_3=a_1+a_2+a_3,\\ \ldots\\ b_n=a_1+a_2+\cdots+a_n.$
Now reduce these numbers mod $n$. At least two will lie in the same class by the pigeonhole principle. If $b_i\equiv b_j\mod n$ for $i<j$ let $T=\{a_{i+1},\ldots, a_j\}$.
This solution was taken from here. The OP can find similar problems there as well.
