A simple discrete math riddle

Question

Let $\mathbb{P}$ be a set of integers. Let $\mathbb{N}$ be the number of the elements in $\mathbb{P}$. Prove that there must be a subset of $\mathbb{P}$ that it's sum is divided by $\mathbb{N}$. Any idea?

Answer 1

Let the integers be $a_1, a_2,\dots,a_N$.

Now, consider the sums $$\begin{align} S_1&=a_1\\ S_2&=a_1+a_2\\ S_3&=a_1+a_2+a_3\\ \vdots\\ S_k&=a_1+a_2+\dots+a_k\\ \vdots\\ S_N&=a_1+a_2+\dots a_N \end{align}$$

Now, if someone of $S_k$ is $0\pmod N$ then we are done.

If none of then is $0\pmod N$, then all the $S_i$'s can be $1,2,\dots,N-1\pmod N$. But as there are there are $N$ $S_i$'s, there must be some $1\le j\le k\le N$ such that $$S_j\equiv S_k\pmod N\\\implies a_{j+1}+a_{j+2}+\dots+a_k\equiv 0\pmod N$$

Thus we have found $\{a_{j+1},\dots,a_k\}$ as the subset of $P$, whose sum of elements is divisible by $N$.