Results 1 to 8 of 8

Math Help - Pigeon-hole Principle (2)

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

    Pigeon-hole Principle (2)

    (a) Let n >= 2. We select n + 1 different integers from the set {1, 2, ..., 2n}. Is it true that there will always be two among the selected integers so that one of them is equal to twice the other?
    (b) Is it true that there will always be two among the selected integers so that one is a multiple of the other?

    My attempt:
    (a) is false. A counterexample for n = 5: {1, 3, 4, 5, 7, 9}.
    I think (b) is true but cannot seem to prove it. Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2010
    Posts
    193

    Re: Pigeon-hole Principle (2)

    This says "solved", but I don't see a solution here... I was interested to see if this was correct:

    Let's let A=\{1,2,\ldots ,n\},B=\{n+1,n+2,\ldots ,2n\}. Suppose we wanted to attempt to pick n+1 elements such that no one is a multiple of another. Since |B|=n, at least one choice must come from A. Let's pick x_1\in A. This eliminates at least one possible choice from B; namely, 2x_1. Now there are only n-1 possible choices left in B (at most) and n choices left to make. It follows that we need to choose another x_2\in A, which eliminates at least one more choice from B. Iterating this process, we see that we need to pick every element from A and can't pick anything from B, which is of course bad, since we have only chosen n elements. Of course, we could probably come to a contradiction a bunch of different ways before exhausting all of A, but this seems to work.

    I think this is right. If someone could make sure, that would be great; and if there are better solutions, I'd be interested in seeing those too.
    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 (2)

    Quote Originally Posted by topspin1617 View Post
    Let's pick x_1\in A. This eliminates at least one possible choice from B; namely, 2x_1.
    What if 2x_1 \in 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 (2)

    a) is not true:

    If n=5, 2n=10; {1,2,3,4,5,6,7,8,9,10}

    Now we will pick 6 elements from the above group:

    {1,3,4,5,7,9}


    I didn't see your solution for a...


    An idea for part b)

    I will give the idea via example when n=10.


    n=10 the 2n=20

    X={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 ,20}

    I will divide set X to some subsets:

    A_1={1,2,4,8,16}

    A_2={3,6,9,18}

    A_4={5,10,20}

    A_5={7,14}

    A_6={11}

    A_7={13}

    A_8={17}

    A_9={19}

    If we take 11 elements there must be at least two of the that are in the same set!
    Last edited by Also sprach Zarathustra; August 3rd 2011 at 12:19 PM.
    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 (2)

    Quote Originally Posted by Also sprach Zarathustra View Post
    An idea for part b)

    I will give the idea via example when n=10.


    n=10 the 2n=20

    X={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 ,20}

    I will divide set X to some subsets:

    A_1={1,2,4,8,16}

    A_2={3,6,9,18}

    A_4={5,10,20}

    A_5={7,14}

    A_6={11}

    A_7={13}

    A_8={17}

    A_9={19}

    If we take 11 elements there must be at least two of the that are in the same set!
    6 and 9 are in the same subset but one is not a multiple of the other. Where are 12 and 15?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2010
    Posts
    193

    Re: Pigeon-hole Principle (2)

    Quote Originally Posted by alexmahone View Post
    What if 2x_1 \in A?
    Ugh. Of course.

    Have to think some more.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2010
    Posts
    193

    Re: Pigeon-hole Principle (2)

    Maybe the other guy was on to something up there. For 1\leq r\leq n, let A_r=\{2^k\cdot (2r-1)\mid k\geq 0, 2^k\cdot (2r-1)\leq 2n\}. Certainly every element of \{1,2,\ldots ,2n\} is in at least one of the A_r. (Of course all of the odd numbers are; for the even numbers, factor out the highest power of 2 possible, and see that it is in the set corresponding to the remaining odd factor.) Note that there are exactly n of these sets A_r. Also, notice that for any fixed r, every element of A_r has a divisibility relation with every other element of that same set. This means that, if we were picking elements which share no such relation, the best we could do is pick one element from each set. Since there are only n sets, the best we could possibly do is pick n elements.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Pigeon-hole Principle (2)

    Quote Originally Posted by topspin1617 View Post
    Maybe the other guy was on to something up there. For 1\leq r\leq n, let A_r=\{2^k\cdot (2r-1)\mid k\geq 0, 2^k\cdot (2r-1)\leq 2n\}. Certainly every element of \{1,2,\ldots ,2n\} is in at least one of the A_r. (Of course all of the odd numbers are; for the even numbers, factor out the highest power of 2 possible, and see that it is in the set corresponding to the remaining odd factor.) Note that there are exactly n of these sets A_r. Also, notice that for any fixed r, every element of A_r has a divisibility relation with every other element of that same set. This means that, if we were picking elements which share no such relation, the best we could do is pick one element from each set. Since there are only n sets, the best we could possibly do is pick n elements.
    Yeah, that's right. Good job!
    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

/mathhelpforum @mathhelpforum