Results 1 to 2 of 2

Thread: A divisible subset

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    A divisible subset

    I got the following from a book:

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

    $\displaystyle \text{Proof:}$

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

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

    We consider two cases:

    Case 1:

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

    Case 2:

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

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

    Therefore,

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

    and so

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

    Hence

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

    Remark:

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

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

    $\displaystyle \Sigma_{i=1}^k a_i \not\equiv 0\: \text{(mod n)}$ implies the existence of $\displaystyle \Sigma_{i=1}^s \equiv r\: \text{(mod n)}$ and $\displaystyle \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

    $\displaystyle \Sigma_{i=1}^k a_i \not\equiv 0\: \text{(mod n)}$ implies the existence of $\displaystyle \Sigma_{i=1}^s \equiv r\: \text{(mod n)}$ and $\displaystyle \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 $\displaystyle n-1$ possible values for $\displaystyle \Sigma_{i=1}^k a_i \mod n$, since the value $\displaystyle 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: Feb 20th 2013, 09:32 AM
  2. Replies: 8
    Last Post: Jul 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: Oct 24th 2010, 09:04 PM
  4. Replies: 1
    Last Post: May 7th 2010, 11:49 PM
  5. Replies: 5
    Last Post: Jan 1st 2010, 01:59 AM

Search Tags


/mathhelpforum @mathhelpforum