3
$\begingroup$

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

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

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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.