Results 1 to 10 of 10

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

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    @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
    185
    Thanks
    13
    Quote Originally Posted by tonio View Post
    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.
    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; September 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 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.
    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 {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.
    Last edited by melese; September 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
    677
    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 {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
    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: August 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: March 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: January 28th 2007, 05:25 PM

Search Tags


/mathhelpforum @mathhelpforum