Math Help - Any set of m positive integers contains a nonempty subset whose sum is ...

1. Any set of m positive integers contains a nonempty subset whose sum is ...

Any set of m positive integers contains a nonempty subset whose sum is a
multiple of m.
Proof. Suppose a set T has no nonempty subset with sum divisible by m. Look at the
possible sums mod m of nonempty subsets of T. Adding a new element a to T will give at
least one new sum mod m, namely the least multiple of a which does not already occur.
Therefore the set T has at least |T| distinct sums mod m of nonempty subsets and |T| < m.

Please help me understand the proof. I know modular number theory etc, but I do not understand the logics here.

Thanks

2. Originally Posted by oleholeh
Any set of m positive integers contains a nonempty subset whose sum is a
multiple of m.
Proof. Suppose a set T has no nonempty subset with sum divisible by m. Look at the
possible sums mod m of nonempty subsets of T. Adding a new element a to T will give at
least one new sum mod m, namely the least multiple of a which does not already occur.
Therefore the set T has at least |T| distinct sums mod m of nonempty subsets and |T| < m.

Please help me understand the proof. I know modular number theory etc, but I do not understand the logics here.

Thanks

I would hardly call the above "proof" of anything...I'd rather go as follows:

let $T=\{a_1,\ldots,a_m\}\,,\,\,a_i\in\mathbb{N}$ . Now,

1) if $\exists i\,\,s.t.\,\,\,a_i=0\!\!\pmod m$ , then the subset $\{a_i\}$ does the trick;

2) if $a_i=-a_j\!\!\pmod m\,,\,1\leq i\neq j\leq m$ , then $\{a_i,\,a_j\}$ does it;

3) Thus, we can reduce the problem where the set $T$ contains m natural numbers all of

which aren't multiples of m nor are there couples like in (2) above.

But then in $T$ cannot be more than $[\frac{m}{2}]$ equivalence classes modulo m, otherwise

condition (2) above applies.

Try now to take it from here

Tonio

3. @Tonio - A little more push please? Can't reason out further from the fact which you proved that T has at most [m/2] equivalence classes. Thanks

4. Originally Posted by tonio
But then in $T$ cannot be more than $[\frac{m}{2}]$ equivalence classes modulo m, otherwise
condition (2) above applies.
Tonio
Would you be so kind to elaborate this for me, please? Its late in the afternoon, I just had my lunch, and the blood is rushing away from brain into my stomach.

5. Edit: Sorry I made a mistake.

6. Well, I figured it out even before I checked for responses here (it happens a lot ;p). Anyway, assume that T does not have a subset whose sum is 0 mod m. Then take a T of size one (which does not equal 0 mod m of course) For every additional element you add to this T, the sum now becomes a mod m that has not appeared before. Why? Otherwise for T_1 and T_2 with same sum mod m, you take the subset of elements that are on T_2 but not T_1, and that new subset = 0 mod m. Now, when T has reached the size m, the collection of T's must contain m unique possible values of mod m, meaning all including 0. Contradiction.

7. Originally Posted by oleholeh
Well, I figured it out even before I checked for responses here (it happens a lot ;p). Anyway, assume that T does not have a subset whose sum is 0 mod m. Then take a T of size one (which does not equal 0 mod m of course) For every additional element you add to this T, the sum now becomes a mod m that has not appeared before. Why? Otherwise for T_1 and T_2 with same sum mod m, you take the subset of elements that are on T_2 but not T_1, and that new subset = 0 mod m. Now, when T has reached the size m, the collection of T's must contain m unique possible values of mod m, meaning all including 0. Contradiction.
The logic is obscured because your writing is not very clear. For example, "the sum now becomes a mod m that has not appeared before" -- what sum? I would rewrite as follows.

You want to build a set $\displaystyle T$ with $\displaystyle |T| = m$ and no non-empty subset having a sum divisible by $\displaystyle m$. So you start with $\displaystyle T_1$ with size 1, then add an element to get $\displaystyle T_2$ with size 2, etc. Associate with $\displaystyle T_i$ all its non-empty subsets $\displaystyle S_{i,1}, S_{i,2},\,\ldots\,, S_{i,2^i-1}$. Now consider creating $\displaystyle T_{i+1}$ by taking $\displaystyle \{x\} \cup T_i$ for some element $\displaystyle x$. Suppose the sum of $\displaystyle T_{i+1}$ is equivalent to the sum of some $\displaystyle S_{i,j}$ mod $\displaystyle m$. Then we take $\displaystyle T_{i+1} - S_{i,j}$ and get a non-empty subset of $\displaystyle T_{i+1}$ with sum divisible by $\displaystyle m$. Thus in order to assure that there are no non-empty subsets with sum divisible by $\displaystyle m$, we must create a new non-empty subset sum mod $\displaystyle m$. The proof proceeds as previously mentioned.

Perhaps a bit wordy... but I think it's an improvement.

8. The underlying idea is Dirichlet's Box Principle, also known as The Pigeonhole Principle.

Let ${a_1, a_2, ..., a_m}$ be a set of $m$ positive integers.
Denote $S_1=a_1, S_2=a_1+a_2, ..., S_m=a_1+a_2+\cdots+a_m$. Suppose that none of these sums is divisible by $m$.
The sums give at most $m-1$ distinct remainders when divided by $m$, namely, $1, 2, ..., m-1$. But since there are $m$ sums, at least two of them have the same remainder when divided by $m$, say $S_i$ and $S_j$, where $j>i$. Now $S_j-S_i$ is divisible by $m$ and also $S_j-S_i=a_{i+1}+\cdots+a_j$.

9. Thanks. Very neat indeed.

10. Originally Posted by melese
The underlying idea is Dirichlet's Box Principle, also known as The Pigeonhole Principle.

Let ${a_1, a_2, ..., a_m}$ be a set of $m$ positive integers.
Denote $S_1=a_1, S_2=a_1+a_2, ..., S_m=a_1+a_2+\cdots+a_m$. Suppose that none of these sums is divisible by $m$.
The sums give at most $m-1$ distinct remainders when divided by $m$, namely, $1, 2, ..., m-1$. But since there are $m$ sums, at least two of them have the same remainder when divided by $m$, say $S_i$ and $S_j$, where $j>i$. Now $S_j-S_i$ is divisible by $m$ and also $S_j-S_i=a_{i+1}+\cdots+a_j$.
Yea basically what i was trying to say, but u said it better