# 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??

## 1 Answer

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
• good point if you consider the empty case as a valid solution. – Mohammad Riazi-Kermani Apr 22 '18 at 20:51
• 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
• OK, I got it now! Thanks. – Mohammad Riazi-Kermani Apr 23 '18 at 1:09