Results 1 to 6 of 6

Math Help - Pigeon-hole Principle

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Pigeon-hole Principle

    We chose n + 2 numbers from the set 1, 2, ..., 3n. Prove that there are always two among the chosen numbers whose difference is more than n but less than 2n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Pigeon-hole Principle

    Quote Originally Posted by alexmahone View Post
    We chose n + 2 numbers from the set 1, 2, ..., 3n. Prove that there are always two among the chosen numbers whose difference is more than n but less than 2n.
    The solution is from the net, in "my words",http://www.worldscibooks.com/etextbo...177_chap01.pdf

    page: 16, #11



    First, denote the largest chosen number from [1,3n] as 3n-a, a can be 0.

    Second, we add a to our all chosen numbers, that would not change the result:

    Say, if x_i and x_j are chosen ones, x_i-x_j=t; then by adding to x_i and x_j a we will still get (x_i+a)-(x_j+a)=t.

    So by adding a to the largest chosen, 3n-a, we will get 3n.

    Now, we have two cases, one is if one of n+1 other chosen numbers is from [n+1,2n-1],

    if so, we are done, if x_k\in [n+1,2n-1], then n<3n-x_k<2n.

    The second case is if the other n+1 chosen numbers are from [1,n] and [2n,3n-1].

    Now, consider the following n pairs:

    (1,2n), (2,2n+1),...,(i,i+2n-1),...,(n,3n-1)

    (If (x,y) is a asome above pair then x is from [1,n] and y is from [2n,3n-1])

    So, we have n pairs, but we choose n+1 numbers, then there must to be one pair with two chosen elements.

    Say, that is (k,k+2n-1), x=k, y=k+2n-1,

    n<y-x=k+2n-1-k=2n-1<2n
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Pigeon-hole Principle

    How come "a" doesn't figure in the rest of the solution?

    For example, how do you consider the pair (1, 2n)? Shouldn't the smallest number of the set now be "a"?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Pigeon-hole Principle

    Quote Originally Posted by alexmahone View Post
    How come "a" doesn't figure in the rest of the solution?

    For example, how do you consider the pair (1, 2n)? Shouldn't the smallest number of the set now be "a"?

    The pair (1,2n) is ordered set that contains two elements, one from [1,n] and one from [2n,3n-1].

    (1,2n) - 1 is from closed interval [1,n] ; 2n is from closed interval [2n,3n-1].
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Pigeon-hole Principle

    Quote Originally Posted by Also sprach Zarathustra View Post
    The pair (1,2n) is ordered set that contains two elements, one from [1,n] and one from [2n,3n-1].

    (1,2n) - 1 is from closed interval [1,n] ; 2 is from closed interval [2n,3n-1].
    But I thought you added "a" to all the numbers in the second step. So shouldn't we have (1+a, 2n+a) etc?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Pigeon-hole Principle

    Quote Originally Posted by alexmahone View Post
    But I thought you added "a" to all the numbers in the second step. So shouldn't we have (1+a, 2n+a) etc?

    Okay!

    The adding a needed only at the first stage, the purpose was eliminate closed interval [n+1,2n-1].
    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: 1
    Last Post: July 30th 2011, 02:48 AM
  2. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 04:24 AM
  3. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 02:56 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 03:39 AM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 05:37 PM

Search Tags


/mathhelpforum @mathhelpforum