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

**oleholeh** · September 19th 2010, 07:44 PM

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

**tonio** · September 20th 2010, 03:42 AM

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

**aman_cc** · September 20th 2010, 05:50 AM

@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

**MathoMan** · September 20th 2010, 05:57 AM

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.

**undefined** · September 20th 2010, 07:54 AM

Edit: Sorry I made a mistake.

**oleholeh** · September 20th 2010, 02:58 PM

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.

**undefined** · September 20th 2010, 04:10 PM

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.

**melese** · September 20th 2010, 04:23 PM

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

**aman_cc** · September 20th 2010, 07:09 PM

Thanks. Very neat indeed.

**oleholeh** · September 24th 2010, 06:27 AM

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

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

[SOLVED] Show a nonempty finite subset of R has a max and min

Nonempty Subset of Q

Prove every set in [0,1], A, with positive measure has a non-measurable subset

Positive Integers

Positive Integers

Search Tags