Results 1 to 7 of 7

Thread: Help Combinatorics 2 :)

  1. #1
    Junior Member
    Joined
    May 2018
    From
    gol
    Posts
    25

    Help Combinatorics 2 :)

    Help Combinatorics
    Hello need help while asking

    Of the 2000 numbers in the field 2000≥n≥1 someone chose 1001 different numbers.
    Prove that the 1001 groups that are selected must have two different elements x, y so that y is divisible by x with no remainder.
    thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,455
    Thanks
    1368

    Re: Help Combinatorics 2 :)

    Suppose you choose all the numbers 1001 to 2000 (they cannot divide each other). That is 1000 numbers. You just need to choose one more. For any number you choose in 501 to 1000, if you double it, you get a number in the 1001 to 2000 range. Triple a number in the 334 to 500 range to get a number in the 1001 to 2000 range. You see the pattern here? No matter what number you choose for the last number, it will always divide one of the numbers already chosen.

    I'm guessing this will wind up being a Pigeonhole Principle problem. I'm not seeing the argument yet, but if you think about it, you can probably come up with something.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2018
    From
    gol
    Posts
    25

    Re: Help Combinatorics 2 :)

    I have no idea to start this algebraic.///
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,455
    Thanks
    1368

    Re: Help Combinatorics 2 :)

    Suppose we are trying to pick numbers that are relatively prime. For every number we pick in the 1 to 1000 range, there is at least one number in the 1001 to 2000 range that is a multiple:
    In the 501 to 1000 range, multiply by 2
    In the 334 to 500 range multiply by 3
    In the 226 to 333 range, multiply by 4
    In the 201 to 225 range, multiply by 5,
    Etc.
    So, for each number you pick in the 1 to 1000 range, there is one fewer numbers available in the 1001 to 2000 range to pick. By the Pigeonhole principle, you must pick at least one number in the 1 to 1000 range and at least one number in the 1001 to 2000 range. This is the start of the proof. You will need to construct the logic as to why this matters, but if you try to pick all numbers 1001 to 2000, any number you pick less than that is going to divide one of the numbers in the 1001 to 2000 range. And if you try to "shift" one of the numbers from the 1001 to 2000 range, each number you shift will divide a different number in the 1001 to 2000 range (causing you to need to shift even more numbers). Each time you shift a number from the "upper" range to the "lower" range, you wind up causing another divisor to be added.
    Last edited by SlipEternal; Jun 1st 2018 at 08:02 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    May 2018
    From
    gol
    Posts
    25

    Re: Help Combinatorics 2 :)

    Quote Originally Posted by SlipEternal View Post
    Suppose we are trying to pick numbers that are relatively prime. For every number we pick in the 1 to 1000 range, there is at least one number in the 1001 to 2000 range that is a multiple:
    In the 501 to 1000 range, multiply by 2
    In the 334 to 500 range multiply by 3
    In the 226 to 333 range, multiply by 4
    In the 201 to 225 range, multiply by 5,
    Etc.
    So, for each number you pick in the 1 to 1000 range, there is one fewer numbers available in the 1001 to 2000 range to pick. By the Pigeonhole principle, you must pick at least one number in the 1 to 1000 range and at least one number in the 1001 to 2000 range. This is the start of the proof. You will need to construct the logic as to why this matters, but if you try to pick all numbers 1001 to 2000, any number you pick less than that is going to divide one of the numbers in the 1001 to 2000 range. And if you try to "shift" one of the numbers from the 1001 to 2000 range, each number you shift will divide a different number in the 1001 to 2000 range (causing you to need to shift even more numbers). Each time you shift a number from the "upper" range to the "lower" range, you wind up causing another divisor to be added.
    Hey frined,
    first of all thanks for the help but I understood the principle but I could not bring it to the written expression, forgive if it is exaggerated but can you write me the way and the solution to understand 100%?
    Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,455
    Thanks
    1368

    Re: Help Combinatorics 2 :)

    Quote Originally Posted by yossa View Post
    Hey frined,
    first of all thanks for the help but I understood the principle but I could not bring it to the written expression, forgive if it is exaggerated but can you write me the way and the solution to understand 100%?
    Thanks
    The idea of this forum is to help you formulate ideas to progress in problems where you are stuck. I gave you a framework to describe a solution, but I did not formulate the actual solution. The next step is for you to use what I came up with, get as far as you can, then ask for more help if you need it. It is not conducive for us to do your homework for you.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    May 2018
    From
    gol
    Posts
    25

    Re: Help Combinatorics 2 :)

    You're right, but I do not do homework. I just sharpen the things that are taught in the classroom and solve a lot of exercises. It's like I'm stuck in them, so I ask for help, but thank you so much ))))
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jul 2nd 2011, 07:40 PM
  2. Help with combinatorics.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Feb 7th 2011, 07:30 PM
  3. Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 7th 2009, 05:29 AM
  4. Need help with combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 16th 2009, 09:03 AM
  5. Combinatorics
    Posted in the Statistics Forum
    Replies: 1
    Last Post: Nov 24th 2008, 05:39 PM

/mathhelpforum @mathhelpforum