Results 1 to 6 of 6

Math Help - Combinatorics question

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    2

    Combinatorics question

    Can anyone help me with this problem;

    Let n ≤ 2 be an integer. Given a sequence of n integers a1,
    a2,...,an, show that there exist consecutive terms in the sequence whose sum
    is divisible by n. That is, show that there are i and j, with 1 ≤i j n,
    such that:
    sij= ai + ai + 1 + + aj 0 (mod n)

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    Quote Originally Posted by chad303 View Post
    Can anyone help me with this problem;

    Let n ≤ 2 be an integer. Given a sequence of n integers a1,
    a2,...,an, show that there exist consecutive terms in the sequence whose sum
    is divisible by n. That is, show that there are i and j, with 1 ≤i j n,
    such that:
    sij= ai + ai + 1 + + aj 0 (mod n)

    Thanks
    I think this question needs to be cleaned up a bit? First, it can't be n \leq 2, it has to be n \geq 2. And that s_{ij} equation looks funny. Is it
    s_{ij} = 1 + ~ ... ~ a_i + 1 + ~...~ + a_j or something?

    -Dan
    Last edited by topsquark; December 8th 2007 at 06:38 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    I guess it is

    Attached Thumbnails Attached Thumbnails Combinatorics question-sequence1.gif  
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2007
    Posts
    2

    Question clean up

    The question is fine on my screen, perhaps a font mismatch or something is causing it to be diplayed improperly.
    But yes, the second reply accurately describes the problem.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    If we can find <br />
1 \leqslant j \leqslant n<br />
such that <br />
\sum\limits_{1 \leqslant k \leqslant j} {a_k }  = \dot n we are done

    Suppose we can't find <br />
1 \leqslant j \leqslant n<br />
such that <br />
\sum\limits_{1 \leqslant k \leqslant j} {a_k }  = \dot n

    We have <br />
\sum\limits_{1 \leqslant k \leqslant j} {a_k }  \equiv 1;2;3;...;n - 1\left( {\bmod n} \right)<br />
with <br />
1 \leqslant j \leqslant n<br />

    Then by the pigeon hole principle there are
    j,p \in \mathbb{N}<br />
such that <br />
\sum\limits_{1 \leqslant k \leqslant j} {a_k }  \equiv \sum\limits_{1 \leqslant k \leqslant p} {a_k } \left( {\bmod n} \right),n \geqslant p > j \geqslant 1<br /> <br />

    Thus: <br />
\sum\limits_{1 \leqslant k \leqslant p} {a_k }  - \sum\limits_{1 \leqslant k \leqslant j} {a_k }  \equiv 0\left( {\bmod n} \right) \Rightarrow \sum\limits_{j + 1 \leqslant k \leqslant p} {a_k }  \equiv 0\left( {\bmod n} \right)<br />

    I hope it is ok
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    (I am too lazy to read to uncode the sigma's in Paul's post but here is how I would do it).
    Consider
    b_1=a_1
    b_2=a_1+a_2
    b_3=a_1+a_2+a_3
    ....
    b_n=a_1+a_2+a_3+...+a_n
    There are n such integers for b_k. Now if any one of these leaves remainder of 0 then the proof is complete. Otherwise let we have n-1 remainder (excluding 0) among n integers so two of them leave the same remainder by pigeonholing b_i,b_j with i>j then b_i - b_j = a_{j+1}+...+a_i is divisible by n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 29th 2011, 05:35 AM
  2. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: May 2nd 2011, 03:30 AM
  3. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 24th 2011, 09:19 AM
  4. combinatorics question -- please help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 30th 2009, 11:10 PM
  5. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 10th 2008, 10:21 AM

Search Tags


/mathhelpforum @mathhelpforum