problem related to pigeon hole principle

Question

please help me to solve this using pigeon hole principle

Suppose that S is a set of n integers. Show that one can choose a nonempty subset T of S such that the sum of all elements of T is divisible by n.

thank you

Answer 1

Your question is special case of the following:

Prove that there exist consecutive terms with a sum divisible by n

Here, I explain with an example.

Let's assume $n=4$

and our set is $\{1,3,5,10\}$

Instead of working with numbers, we can work with the remainders. In this case we need to prove that there exist a (consecutive) sequence in remainders $(1,3,1,2)$ That have a sum divisible by $n$. We make sequence of commulative sums of remainders for example for $(1,3,5,10)\equiv(1,3,1,2)$ $$1$$ $$1+3=4 \equiv 0$$ $$1+3+1=5 \equiv 1$$ $$1+3+1+2=7 \equiv 3$$ And we seek for a sum which is congruent to zero. If you found that, that is the answer. In this case that is $1+3$. If you did not find that zero, the remainders of sums can have $(n-1)$ values since there is no zero among them while the number of them is $n$. So two sums have the same value!! In this case, $1$ and $1+3+1=5 \equiv 1$. Therefore, the subtract of these commulative sums still would be a consecutive sum with a remainder zero.

Answer 2

Hint

If the integers are $a_1,a_2,\ldots, a_n$, let, for $0\le k\le n$, $$s_k=\sum_{j=1}^k a_j$$

(Of course, $s_0=0$).

How many different values can have $s_k\pmod n$? Must there be two of them $s_p\equiv s_q\pmod n$? What happens with $s_q-s_p$?