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

  • $\begingroup$ HINT: consider $\{ \sum_{a \in S} a \mod{n} : S \subseteq A \} \subseteq \{ 0, 1, \dots, n-1 \}$. $\endgroup$ – 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.

  • $\begingroup$ 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.. $\endgroup$ – inquisitive May 5 '15 at 11:30
  • $\begingroup$ @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. $\endgroup$ – Mark Bennet May 5 '15 at 11:55
  • $\begingroup$ Thanks a lot! I understood. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.