Remarkable Subset

This is an application of the pigeonhole principle.

Say the numbers in the set are $a_1,a_2,\ldots,a_n$ . If any of these is divisible by $n$ , we're done; so assume from now on that none of them are.

Consider the $n$ sums $s_1=a_1$ , $s_2=a_1+a_2$ , $s_3=a_1+a_2+a_3$ ,..., $s_n=a_1+a_2+\cdots +a_n$ . Again, if any of these sums happens to be divisible by $n$ , we're done, so we can assume that no $s_n$ is a multiple of $n$ .

Now, there are $n$ sums, and exactly $n-1$ non-zero remainders upon division by $n$ . So (by the pigeonhole principle), for some $i<j$ we must have that $s_i\equiv s_j \pmod{n}$

But this means that $n$ divides $s_j-s_i=a_{i+1}+a_{i+2}+\cdots +a_j$ , which gives us a subset that works.

Therefore there must always be a subset whose sum is divisible by $n$ .