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

• And that subset must not be empty? – Jeppe Stig Nielsen Mar 30 '13 at 20:07
• @JeppeStigNielsen is $0\in\mathbb{N}$? – oldrinb Mar 30 '13 at 20:08
• @oldrinb I was referring to the searched-for subset of $A$, not to $A$ itself. $X\subseteq A\subset\mathbb{N}$. – Jeppe Stig Nielsen Mar 30 '13 at 20:21

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$