Results 1 to 2 of 2

Math Help - Pigeonhole Proof

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Pigeonhole Proof

    Prove that for any n+1 integers a1, a2, ..., a(n+1), there exist two of the integers ai and aj with i != j such that ai - aj is divisible by n.

    I know the use of the pigeonhole principle is the way to attack this proof. I just don't know how to show it.

    Any help is greatly appreciated. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Hint - think of remainder when a_i divided by 'n' as holes and a_i's as pigeon.
    How many bins you have?
    How many pigeons?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 14th 2010, 01:12 PM
  2. help me with pigeonhole principle #3
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 06:38 PM
  3. Replies: 7
    Last Post: February 20th 2009, 02:05 PM
  4. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  5. Non-Trivial Proof Using Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2008, 11:26 PM

Search Tags


/mathhelpforum @mathhelpforum