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

Question

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

Answer 1

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$