Results 1 to 2 of 2

Math Help - A divisible subset

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    A divisible subset

    I got the following from a book:

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

    \text{Proof:}

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

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

    We consider two cases:

    Case 1:

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

    Case 2:

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

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

    Therefore,

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

    and so

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

    Hence

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

    Remark:

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

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

    \Sigma_{i=1}^k a_i \not\equiv 0\: \text{(mod n)} implies the existence of \Sigma_{i=1}^s \equiv r\: \text{(mod n)} and \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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by novice View Post
    I got the following from a book:

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

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

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: February 20th 2013, 09:32 AM
  2. Replies: 8
    Last Post: July 3rd 2011, 03:55 PM
  3. Proof on Openness of a Subset and a Function of This Subset
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 24th 2010, 09:04 PM
  4. Replies: 1
    Last Post: May 7th 2010, 11:49 PM
  5. Replies: 5
    Last Post: January 1st 2010, 01:59 AM

Search Tags


/mathhelpforum @mathhelpforum