# A divisible subset

• Jun 2nd 2010, 06:21 PM
novice
A divisible subset
I got the following from a book:

Let $n \in \mathbb{N}$. Show that for every set S of $n$ integers, there is a nonempty subset $\color{blue}T$ of $\color{blue}S$ such that $\color{blue}n$ divides the sum of elements of $\color{blue}T$.

$\text{Proof:}$

Let $S_k=\{a_1,a_2,...,a_k\}$ for each integer $k$ with $1\leq k \leq n$. For each integer $k(1\leq k \leq n),$

$\Sigma_{i=1}^k a_i\equiv r \: \text{(mod n)}$ for some integer $r$, where $0 \leq r \leq n-1$.

We consider two cases:

Case 1:

$\Sigma_{i=1}^k a_i \equiv 0\: \text{(mod n)}$ for some integer $k$. Then $n|\Sigma_{i=1}^k$, that is, $n$ divides the sum of the elements $S_k$.

Case 2:

$\Sigma_{i=1}^k a_i \not\equiv 0\: \text{(mod n)}$ for all integer $k (1\leq k \leq n)$.

Hence there exist integers there exist integers $s$ and $t$ with $1 such that $\Sigma_{i=1}^s \equiv r\: \text{(mod n)}$ and $\Sigma_{i=1}^t \equiv r\: \text{(mod n)}$ for integer $r$ with $1\leq r \leq n-1$.

Therefore,

$\Sigma_{i=1}^s a_i \equiv \Sigma_{i=1}^t a_i \: \text{(mod n)}$

and so

$n|(\Sigma_{i=1}^t a_i - \Sigma_{i=1}^s a_i )$

Hence

$n|\Sigma_{i=s+1}^s a_i )$

Remark:

1. I have tested a set of $n$ elements on the computer and found that at least one of the $2^n-1$ nonempty subsets is divisible by $n$.

2. In regard to case 2 in the proof above, I can't see how

$\Sigma_{i=1}^k a_i \not\equiv 0\: \text{(mod n)}$ implies the existence of $\Sigma_{i=1}^s \equiv r\: \text{(mod n)}$ and $\Sigma_{i=1}^t \equiv r\: \text{(mod n)}$. It might be true by chance.

Question: Does anyone here have a better proof than this?
• Jun 2nd 2010, 07:19 PM
Bruno J.
Quote:

Originally Posted by novice
I got the following from a book:

2. In regard to case 2 in the proof above, I can't see how

$\Sigma_{i=1}^k a_i \not\equiv 0\: \text{(mod n)}$ implies the existence of $\Sigma_{i=1}^s \equiv r\: \text{(mod n)}$ and $\Sigma_{i=1}^t \equiv r\: \text{(mod n)}$. It might be true by chance.

Question: Does anyone here have a better proof than this?

What do you mean, true by chance?

There are only $n-1$ possible values for $\Sigma_{i=1}^k a_i \mod n$, since the value $0$ is never taken; by the pigeonhole principle, two of the values must coincide.

I don't think there is a better proof. I believe that this theorem and its proof are by Erdös, and, in fact, I think that it appears in "Proofs from the Book" : meaning that a better proof is incredibly unlikely!