Results 1 to 4 of 4

Math Help - Pigeonhole Principle

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    4

    Pigeonhole Principle

    Dear readers,

    I'm quite stucked with this below question.

    If the remainder is 0 hen an integer a is divided by an integer b, we say that a is divisible by b. Given 27 distinct integers, prove that there must be 2 integers whose sum or difference is divisible by 50.

    Can anyone help me with this?

    Best regards,
    Roland
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by iloveher85 View Post
    Dear readers,

    I'm quite stucked with this below question.

    If the remainder is 0 hen an integer a is divided by an integer b, we say that a is divisible by b. Given 27 distinct integers, prove that there must be 2 integers whose sum or difference is divisible by 50.

    Can anyone help me with this?

    Best regards,
    Roland
    Hi Roland,

    Actually, if I have this figured out correctly, 26 integers are enough.

    Lets say the 26 integers are x_1, x_2, \dots , x_{26}. We may assume without loss of generality that if x is in the set then x is not; otherwise we would have x + (-x) = 0, which is divisible by 50, and we would be through. Consider the expanded set made by throwing in the negatives of the original integers, i.e.

     x_1, x_2, \dots , x_{26}, -x_1, -x_2, \dots , -x_{26}.

    This set contains at least 2 * 26 1 = 51 distinct integers, taking into account the possibility that one of the integers might be 0, in which case x and x are the same.

    Now place the integers into pigeonholes based on their residue class mod 50, i.e. if the remainder on dividing x by 50 is j, then place x in the jth pigeonhole. Then there are 50 pigeonholes, numbered 0 to 49, so some pigeonhole must contain at least two integers, say \pm x_i and \pm x_j. If the two \pms are the same (two +s or two s), then x_i + x_j is divisible by 50. If the two \pms are different (+ and or and +), then x_i - x_j is divisible by 50.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    4
    After going out and take a breath,

    I realise it needs 27 integers.

    Assuming each pigeon hole contains 0, 1, 2, 3, 4, 5, 6, 7.....25

    We have 26 holes.
    thereafter, any number going into the hole will make the sum or difference divisible by 50.

    Therefore Max(27/26 ) = 2
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Oops, you are right, 27 integers are required! I see the problem with my first try-- it breaks down if x_i and -x_i end up in the same residue class. So here is a revised proof that avoids that problem, I think:

    Lets start by thinking about how many of the integers can be multiples of 25. If there are 3 or more multiples of 25, say 25a, 25b, and 25c, then at least 2 of a, b, and c must have the same parity, i.e. both even or both odd. Lets say its a and b that have the same parity; then 25a 25b is an even multiple of 25, i.e. a multiple of 50, and were done. So we may assume that at most 2 of the set are multiples of 25. Lets discard those two integers (because they would cause problems in the proof below), so we still have at least 25 integers, none of which are a multiple of 25.

    Lets say the remaining 25 integers are x_1, x_2, \dots , x_{25}. We may assume without loss of generality that if x is in the set then x is not; otherwise we would have x + (-x) = 0, which is divisible by 50, and we would be through. Consider the expanded set made by throwing in the negatives of the original integers, i.e.

     x_1, x_2, \dots , x_{25}, -x_1, -x_2, \dots , -x_{25}.

    This set contains 50 distinct integers.

    Now place the integers into pigeonholes based on their residue class mod 50, i.e. if the remainder on dividing x by 50 is j, then place x in the jth pigeonhole. We exclude the residue class 0 because we earlier removed any integers which were multiples of 25. Then there are 49 pigeonholes, numbered 1 to 49, so some pigeonhole must contain at least two integers, say \pm x_i and \pm x_j. We know i \neq j because otherwise we would have x_i and -x_i in the same residue class, which would imply 2 x_i is a multiple of 50, which would imply x_i is a multiple of 25. (This is why we excluded multiples of 25 earlier.) If the two \pms are the same (two +s or two s), then x_i + x_j is divisible by 50. If the two \pms are different (+ and or and +), then x_i - x_j is divisible by 50.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum