Results 1 to 7 of 7

Math Help - application of pigeonhole principle

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    22

    application of pigeonhole principle

    It is given 13 integers c_1,c_2,...,c_{13} (some of them may be the same). Use pigeonhole principle to prove that there exist i and j with 0<i<j<=13 such that
    c_{i+1}+c_{i+2}+...+c_j is divisible by 13
    for example, c_4+c_5+c_6+c_7 is divisible by 13.
    (Hint:consider the following 13 integers
    n_1=c_1
    n_2=c_1+c_2
    .
    .
    .
    n_{13}=c_1+c_2+...+c_{13}
    and their remainder when divided by 13)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,965
    Thanks
    1785
    Awards
    1

    Re: application of pigeonhole principle

    Quote Originally Posted by maoro View Post
    It is given 13 integers c_1,c_2,...,c_{13} (some of them may be the same). Use pigeonhole principle to prove that there exist i and j with 0<i<j<=13 such that
    [CENTER] c_{i+1}+c_{i+2}+...+c_j is divisible by 13
    [LEFT]for example, c_4+c_5+c_6+c_7 is divisible by 13.
    (Hint:consider the following 13 integers
    The idea behind this proof is that if two numbers have the same remainder when divided by 13 then there difference is divisible by 13.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    22

    Re: application of pigeonhole principle

    But how this question is related to the pigeonhole principle?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,965
    Thanks
    1785
    Awards
    1

    Re: application of pigeonhole principle

    Quote Originally Posted by maoro View Post
    But how this question is related to the pigeonhole principle?
    Of course, we use the pigeonhole principle.
    The reminders of the of the n_k when divided by 13 are the the pigeonholes. The n_k are the pigeons.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2011
    Posts
    22

    Re: application of pigeonhole principle

    I got you mean.
    Suppose n_k is 14,then its remainder is 1 when n_k is divided by 13
    => there is one pigeonhole containing more than 1 pigeon.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2011
    Posts
    22

    Re: application of pigeonhole principle

    But how about if all of n_i is not divisible by 13?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,965
    Thanks
    1785
    Awards
    1

    Re: application of pigeonhole principle

    Quote Originally Posted by maoro View Post
    But how about if all of n_i is not divisible by 13?
    That means the zero pigeonhole some n_j so it is divisible by 13.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeonhole principle.
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 9th 2010, 07:24 AM
  2. [SOLVED] Application of the Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 19th 2009, 06:47 PM
  3. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 26th 2008, 10:09 AM
  4. Pigeonhole principle?
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: October 16th 2008, 11:08 AM
  5. Pigeonhole principle?
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: December 9th 2007, 09:58 AM

Search Tags


/mathhelpforum @mathhelpforum