Results 1 to 3 of 3

Math Help - Proving A Division Property By Employing The Pigeon-Hole Pricinple

  1. #1
    Member
    Joined
    May 2011
    Posts
    178
    Thanks
    6

    Proving A Division Property By Employing The Pigeon-Hole Pricinple


    Here is the problem: Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.

    Here is the solution:

    Let a, a+1,...,a+n-1 be the integers in the sequence. The integers (a+i) \mod n, i=0,1,2...,n-1, are distinct because 0< (a+j)-(a+k)<n whenever 0 \le k < j < n-1. Because there are n possible values for (a+i) \mod n and there are n different integers integers in the set, each of these values is taken exactly once. It follows that there is exactly one integer in the sequence that is divisible by n.


    Something I don't quite understand: How does
    0< (a+j)-(a+k)<n make the values calculated from the modulus distinct? Also, what is the motivation
    for
    0< (a+j)-(a+k)<n? Why are we allowed to use this fact?

    Last edited by Bashyboy; April 23rd 2013 at 12:31 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,978
    Thanks
    1643

    Re: Proving A Division Property By Employing The Pigeon-Hole Pricinple

    Quote Originally Posted by Bashyboy View Post

    Here is the problem: Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.

    Here is the solution:

    Let a, a+1,...,a+n-1 be the integers in the sequence. The integers (a+i) \mod n, i=0,1,2...,n-1, are distinct because 0< (a+j)-(a+k)<n whenever 0 \le k < j < n-1. Because there are n possible values for (a+i) \mod n and there are n different integers integers in the set, each of these values is taken exactly once. It follows that there is exactly one integer in the sequence that is divisible by n.


    Something I don't quite understand: How does
    0< (a+j)-(a+k)<n make the values calculated from the modulus distinct?

    Since the difference of any two such number is NOT 0, they cannot be equal.
    Also, what is the motivation
    for
    0< (a+j)-(a+k)<n? Why are we allogerwed to use this fact?

    You are told that " 0 \le k < j < n-1".

    (a+ j)- (a+ k)= j- k. It is greater than 0 because j is larger than k. It is less than n because j- k is less than j which is itself less than n.
    Last edited by HallsofIvy; April 23rd 2013 at 01:31 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Proving A Division Property By Employing The Pigeon-Hole Pricinple

    Quote Originally Posted by Bashyboy View Post
    How does 0< (a+j)-(a+k)<n make the values calculated from the modulus distinct?
    Quote Originally Posted by HallsofIvy View Post
    Since the difference of any two such number is NOT 0, they cannot be equal.
    I would rather say the following. If j > k and (a + j) mod n = (a + k) mod n, then (a + j) - (a + k) = 0 mod n, i.e., (a + j) - (a + k) is a multiple of n. This means that either (a + j) - (a + k) = 0 or (a + j) - (a + k) ≥ n. If we exclude both of these options, this would mean that (a + j) mod n ≠ (a + k) mod n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon Hole principle
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2009, 06:13 AM
  2. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 07:22 PM
  3. pigeon-hole
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 01:41 PM
  4. Pigeon Hole problem!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 29th 2008, 09:10 AM
  5. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 30th 2007, 08:37 AM

Search Tags


/mathhelpforum @mathhelpforum