A divisible subset

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

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

$\displaystyle \text{Proof:}$

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

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

We consider two cases:

Case 1:

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

Case 2:

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

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

Therefore,

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

and so

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

Hence

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

Remark:

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

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

$\displaystyle \Sigma_{i=1}^k a_i \not\equiv 0\: \text{(mod n)}$ implies the existence of $\displaystyle \Sigma_{i=1}^s \equiv r\: \text{(mod n)}$ and $\displaystyle \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, 06: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

$\displaystyle \Sigma_{i=1}^k a_i \not\equiv 0\: \text{(mod n)}$ implies the existence of $\displaystyle \Sigma_{i=1}^s \equiv r\: \text{(mod n)}$ and $\displaystyle \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 $\displaystyle n-1$ possible values for $\displaystyle \Sigma_{i=1}^k a_i \mod n$, since the value $\displaystyle 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!