Results 1 to 5 of 5

Math Help - Pigeon Hole Principle

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    4

    Pigeon Hole Principle

    I'm pretty sure that I should apply the pigeon hole principle, but I'm not sure exactly how.
    Let a_i with i ranging from 1 through n be a sequence of integers (both positive and negative, not necessarily all different). Prove that there exists integers j and k with 1 <= j <= k <= n such that the sum starting from a_j and ending at a_k (ie, the sum of some subsequence of the sequence) sums to a multiple of n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2009
    Posts
    4
    Perhaps we consider the remainders of the members of the sequence after we divide by n. The only possible values for remainders are less than n and greater than 1 (otherwise, we'd be done), and we have n numbers, so at least two members of the sequence have the same remainder.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by waddlyeli View Post
    I'm pretty sure that I should apply the pigeon hole principle, but I'm not sure exactly how.
    Let a_i with i ranging from 1 through n be a sequence of integers (both positive and negative, not necessarily all different). Prove that there exists integers j and k with 1 <= j <= k <= n such that the sum starting from a_j and ending at a_k (ie, the sum of some subsequence of the sequence) sums to a multiple of n
    Hint:

    Consider the n sums \sum_{i=1}^j a_i for j = 1, 2, ..., n.

    If any one of these sums is zero, modulo n, we are done. Otherwise, each of the sums must fall in one of the congruence classes 1, 2, ..., n-1 modulo n. There are n sums and only n-1 congruence classes, so there must be some congruence class that contains at least two of the sums. And then...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2009
    Posts
    4
    Ah, I see. If two of the sums add up to numbers in the same equivalence class, then clearly subtracting the smaller sum from the bigger sum results in a number congruent to n, modulo n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    This nice little theorem is due to Erdös.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 05:24 AM
  2. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 03:56 AM
  3. Pigeon Hole Principle Help!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 17th 2008, 12:14 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 04:39 AM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 06:37 PM

Search Tags


/mathhelpforum @mathhelpforum