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.

Re: Help Combinatorics 2 :)

I have no idea to start this algebraic.///

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.

Re: Help Combinatorics 2 :)

Quote:

Originally Posted by

**SlipEternal** 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 :)

Re: Help Combinatorics 2 :)

Quote:

Originally Posted by

**yossa** 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.

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 :)))))