1

I need some help with the following problem:

Question: Let $n \in \mathbb{N}$ and $A$ $\in$ {$a_1,a_2,\ldots,a_n$} such that there are $n$ integers in $A$. Prove that there exists a subset $S$ of $A$ such that the sum of the elements in $S$ is divisible by $n$.

I have no idea where to begin for this problem, since we have not learned to solve anything similar to this in class. I have encountered a problem that's...somewhat similar, but that problem used pigeonhole principle, which in this case I doubt it will work. But I shall try to do this on my own as best as I can based on my limited knowledge.

Attempted Solution: Suppose $S \subseteq A$ and let $S_k =$ the sum of all the elements in the set $S$. And assume that $S_k \ne 0$ and $n \ne 1$, this is because any value can divide $0$ and $1$ can divide any value. Since $S$ consists of even and/or odd integers, then we know that $S_k$ can be either even or odd. Since the value $n$ can take on either even or odd, then there must be a subset $S$ of $A$ such that $n|S_k$.

I will appreciate it very much if anyone can point out the flaws in my reasoning. Also, are there any merits in my solution at all? Or am I completely off the track?

Sanguine Salvo
  • 13

1 Answers1

2

Say we have $n$ integers $$a_1,a_2,\ldots,a_{n-1},a_n$$ Now, define the sequence $b_1,b_2,\ldots, b_{n-1},b_n$ as: $$b_k=\sum_{i=1}^{k}a_i$$ If all of these are incongruent modulo $n$, then one of them must be congruent to $0$ modulo $n$ and thus divisible by $n$, so we are done.

Suppose they're not all different modulo $n$. Now, we have $l>m$ such that $$b_l\equiv b_m\pmod n$$ Now: $$b_l-b_m=\sum_{i=m+1}^{l}a_i\equiv 0\pmod n$$ and we are done.

Mastrem
  • 8,331