# Proving that every set $A \subset \Bbb N$ of size $n$ contains a subset $B \subset A$ with $n | \sum_{b \in B} b$

If $n\in \Bbb N$, $A\subset \Bbb N$, $|A|=n$, how to prove that there exists a subset of $A$ such that the summation of its element is divisible by $n$?

#### Solutions Collecting From Web of "Proving that every set $A \subset \Bbb N$ of size $n$ contains a subset $B \subset A$ with $n | \sum_{b \in B} b$"

Let $A = \{ a_1, \ldots, a_n \}$. Consider the numbers $0$, $a_1$, $a_1 + a_2$, $\ldots$, $a_1 + a_2 + \cdots + a_n$ modulo $n$. There are $n+1$ numbers and only $n$ residue classes modulo $n$, so by the pigeonhole principle there exist $i$ and $j$ such that $a_1 + \cdots + a_i$ and $a_1 + \cdots + a_i + \cdots + a_j$ are equal modulo $n$. Hence $n$ divides $a_{i+1} + \cdots + a_j$.

Let $A=\{a_1,a_2,\dots,a_n\}$.

Look at the numbers $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, and so on up to $a_1+a_2+\cdots+a_n$. If two of these sums are congruent modulo $n$, say $a_1+\cdots +a_i$ and $a_1+\cdots +a_j$, where $j\gt i$, then their difference $a_{i+1}+\cdots +a_j$ is congruent to $0$, and we have found a non-empty subset of $A$ with sum divisible by $n$.

On the other hand, if $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, and so on up to $a_1+a_2+\cdots+a_n$ are all distinct modulo $n$, then one of them must be congruent to $0$.

Consider the $\rm\:n\:$ partial sums $\rm\: n_1,\,\ n_1\!+n_2,\,\ n_1\!+n_2\!+n_3,\ \ldots\ (mod\ n).$ If one is $\equiv 0\:$ we’re done, else two are $\,\equiv,\,$ so subtracting them yields a tail sum $\equiv 0.$

Remark $\$ Here’s a similar Pigeonhole argument:  if $\rm\:n\:$ is coprime to $10\,$ then every integer with at least $\rm\:n\:$ digits $\ne 0\:$ has a contiguous digit subsequence that forms an integer $\ne 0\,$ divisible by $\rm\:n.\:$ Hint: pigeonholing, two of the $\rm\:n\!+\!1\:$ numbers $\rm\:0,\ d_1,\ d_2 d_1,\ d_3 d_2 d_1,\, \ldots,\:d_m\!\ldots d_1\:$ must be $\rm\:\equiv\, \ (mod\ n),\:$ so subtracting them $\:\ldots$