# 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).

• HINT: consider $\{ \sum_{a \in S} a \mod{n} : S \subseteq A \} \subseteq \{ 0, 1, \dots, n-1 \}$. – Crostul May 5 '15 at 11:06

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.

• That is my doubt exactly, why are we not considering {a2}, {a3}, .......,{a2, a3}, {a3, a4}......etc as partial sums here? Or may be I am not able to understand the question properly.. – inquisitive May 5 '15 at 11:30
• @inquisitive suppose $a_2$ and $a_4$ give you the same remainder - how does that help you to show that there is a subset with remainder zero? You don't know that their difference is a sum. But if $a_1+a_2$ and $a_1+a_2+a_3+a_4$ give the same remainder, their difference is $a_3+a_4$ which gives a sum with remainder zero. So you need to pick out subsets where you know you can take the difference, and if you have enough of them, the proof goes through. – Mark Bennet May 5 '15 at 11:55
• Thanks a lot! I understood. – inquisitive May 13 '15 at 16:47

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.

• That is my doubt exactly, why are we not considering {a2}, {a3}, .......,{a2, a3}, {a3, a4}......etc as partial sums here? – inquisitive May 5 '15 at 11:29
• Because we don't need them. – wythagoras May 5 '15 at 11:37