Results 1 to 3 of 3

Math Help - Pigeon Hole problem!

  1. #1
    Newbie
    Joined
    Mar 2008
    From
    Maine
    Posts
    13

    Pigeon Hole problem!

    how do i show that in any set of 6 integers, there must be at least two whose difference is divisible by 5?

    thanks.

    Kyle
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by CSkyle View Post
    how do i show that in any set of 6 integers, there must be at least two whose difference is divisible by 5?
    thanks.
    Kyle
    Pigeon Hole Principle
    Observe that if two numbers leave the same remainder with 5, then their difference is divisible by 5. Since there are only 5 distinct remainders possible(i.e{0,1,2,3,4}), in a set of six numbers, at least 2 numbers must leave the same remainder when divided by 5(pigeon hole principle). So the conclusion follows.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Isomorphism View Post
    Pigeon Hole Principle
    Observe that if two numbers leave the same remainder with 5, then their difference is divisible by 5. Since there are only 5 distinct remainders possible(i.e{0,1,2,3,4}), in a set of six numbers, at least 2 numbers must leave the same remainder when divided by 5(pigeon hole principle). So the conclusion follows.
    Nice solution.

    So now you're kenshin! ...i don't want to battle kenshin.

    Glad to see you are a part of TeamJ!

    ...they have cookies with new flavors now?!

    why wasn't i told?! It's not like i'm the one always finishing the cookies, you know!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Pigeon-Hole Problem and an Irrational Root Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2013, 01:18 PM
  2. [SOLVED] Pigeon-hole Principle (2)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 3rd 2011, 01:40 PM
  3. Pigeon Hole Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 18th 2010, 06:53 AM
  4. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 07:22 PM
  5. pigeon-hole
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 01:41 PM

Search Tags


/mathhelpforum @mathhelpforum