# Let S be a set of n integers. Show that there is a subset of S, sum of whose elements is a multiple of n by pigeon hole

I came across a question in the pigeonhole principle that - Let S be a set of n integers. Show that there is a subset of S, the sum of whose elements is a multiple of n by pigeonhole.

How do I solve this question??

Consider the set $$\{ a_1, a_1+a_2, a_1 +a_2 +a_3,...,a_1+a_2+...+a_n\}$$
You have a set of $n$ elements.
If all remainders in dividing by $n$, are different, one of the remainders is $0$ and we are done.
Otherwise two remainders are the same. In this case the difference is a multiple of $n$ and as you see the difference is still a sum of some integers from $1$ to $n$
• +1 However I think it would be natural to consider the set $$\{0,a_1,a_1+a_2,a_1+a_2+a_3,\dots,a_1+a_2+\cdots+a_n\}$$ of $n+1$ elements, so that there is only one case instead of two. – bof Apr 22 '18 at 19:01
• Of course the empty set is not a valid solution. The point is that, if we define $s_k=a_1+a_2+\cdots+a_k$ for $k=0,1,2,\dots,n$ (so that $s_0=0$) then we must have $s_i\equiv sj\pmod n$ for some $0\le i\lt j\le n$ and then we get a (nonempty) solution $a_{i+1}+\cdots+a_j\equiv0\pmod n.$ This is exactly your argument, it is just a neater presentation; the point is that the case $i=0$ does not have to be considered separately, it is just like all the other cases. – bof Apr 23 '18 at 0:30