Results 1 to 10 of 10

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

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    20

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by oleholeh View Post
    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 $\displaystyle T=\{a_1,\ldots,a_m\}\,,\,\,a_i\in\mathbb{N}$ . Now,

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

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

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

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

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

    condition (2) above applies.

    Try now to take it from here

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    @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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2010
    Posts
    186
    Thanks
    13
    Quote Originally Posted by tonio View Post
    But then in $\displaystyle T$ cannot be more than $\displaystyle [\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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Edit: Sorry I made a mistake.
    Last edited by undefined; Sep 20th 2010 at 08:31 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2010
    Posts
    20
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by oleholeh View Post
    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 \displaystyle T$ with $\displaystyle \displaystyle |T| = m$ and no non-empty subset having a sum divisible by $\displaystyle \displaystyle m$. So you start with $\displaystyle \displaystyle T_1$ with size 1, then add an element to get $\displaystyle \displaystyle T_2$ with size 2, etc. Associate with $\displaystyle \displaystyle T_i$ all its non-empty subsets $\displaystyle \displaystyle S_{i,1}, S_{i,2},\,\ldots\,, S_{i,2^i-1}$. Now consider creating $\displaystyle \displaystyle T_{i+1}$ by taking $\displaystyle \displaystyle \{x\} \cup T_i$ for some element $\displaystyle \displaystyle x$. Suppose the sum of $\displaystyle \displaystyle T_{i+1}$ is equivalent to the sum of some $\displaystyle \displaystyle S_{i,j}$ mod $\displaystyle \displaystyle m$. Then we take $\displaystyle \displaystyle T_{i+1} - S_{i,j}$ and get a non-empty subset of $\displaystyle \displaystyle T_{i+1}$ with sum divisible by $\displaystyle \displaystyle m$. Thus in order to assure that there are no non-empty subsets with sum divisible by $\displaystyle \displaystyle m$, we must create a new non-empty subset sum mod $\displaystyle \displaystyle m$. The proof proceeds as previously mentioned.

    Perhaps a bit wordy... but I think it's an improvement.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    The underlying idea is Dirichlet's Box Principle, also known as The Pigeonhole Principle.

    Let $\displaystyle {a_1, a_2, ..., a_m}$ be a set of $\displaystyle m $ positive integers.
    Denote $\displaystyle 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 $\displaystyle m $.
    The sums give at most $\displaystyle m-1 $ distinct remainders when divided by $\displaystyle m $, namely, $\displaystyle 1, 2, ..., m-1$. But since there are $\displaystyle m $ sums, at least two of them have the same remainder when divided by $\displaystyle m $, say $\displaystyle S_i $ and $\displaystyle S_j $, where $\displaystyle j>i $. Now $\displaystyle S_j-S_i $ is divisible by $\displaystyle m $ and also $\displaystyle S_j-S_i=a_{i+1}+\cdots+a_j$.
    Last edited by melese; Sep 20th 2010 at 04:39 PM. Reason: superflous words
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Thanks. Very neat indeed.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2010
    Posts
    20
    Quote Originally Posted by melese View Post
    The underlying idea is Dirichlet's Box Principle, also known as The Pigeonhole Principle.

    Let $\displaystyle {a_1, a_2, ..., a_m}$ be a set of $\displaystyle m $ positive integers.
    Denote $\displaystyle 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 $\displaystyle m $.
    The sums give at most $\displaystyle m-1 $ distinct remainders when divided by $\displaystyle m $, namely, $\displaystyle 1, 2, ..., m-1$. But since there are $\displaystyle m $ sums, at least two of them have the same remainder when divided by $\displaystyle m $, say $\displaystyle S_i $ and $\displaystyle S_j $, where $\displaystyle j>i $. Now $\displaystyle S_j-S_i $ is divisible by $\displaystyle m $ and also $\displaystyle S_j-S_i=a_{i+1}+\cdots+a_j$.
    Yea basically what i was trying to say, but u said it better
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Show a nonempty finite subset of R has a max and min
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Aug 31st 2011, 03:17 PM
  2. Nonempty Subset of Q
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2011, 07:12 PM
  3. Replies: 3
    Last Post: Mar 14th 2010, 07:58 AM
  4. Positive Integers
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: May 31st 2007, 01:48 PM
  5. Positive Integers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Jan 28th 2007, 05:25 PM

Search Tags


/mathhelpforum @mathhelpforum