# Help Combinatorics 2 :)

• Jun 1st 2018, 05:52 AM
yossa
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.
• Jun 1st 2018, 06:23 AM
SlipEternal
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.
• Jun 1st 2018, 06:52 AM
yossa
Re: Help Combinatorics 2 :)
I have no idea to start this algebraic.///
• Jun 1st 2018, 07:56 AM
SlipEternal
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.
• Jun 3rd 2018, 10:33 AM
yossa
Re: Help Combinatorics 2 :)
Quote:

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 :)
• Jun 4th 2018, 04:20 AM
SlipEternal
Re: Help Combinatorics 2 :)
Quote:

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.
• Jun 4th 2018, 04:48 AM
yossa
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 :)))))