2: Of the 2000 numbers in the field 2000≥n≥1 someone chose 1001 different numbers...

Y

yossa

New member
Joined
May 18, 2018
Messages
25
2: Of the 2000 numbers in the field 2000≥n≥1 someone chose 1001 different numbers...

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.
 
yossa said:
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.
Click to expand...

I'm not sure I understand the question. Is there one set of 1001 numbers, or are there 1001 sets? The latter doesn't make sense.

So I'll suppose we have one set of 1001 numbers. We want to show that there must be at least one pair of numbers in the set, one of which is a multiple of the other.

I would start by thinking what it would take to make a set that does not contain any such pairs. Can it contain 1? Can it contain 2?

If that doesn't help (and I think it will), my next line of thinking would involve the pigeonhole principle, as the problem sounds very much like that. Is that something you have learned?

What ideas do you have?
 
Dr.Peterson said:
I'm not sure I understand the question. Is there one set of 1001 numbers, or are there 1001 sets? The latter doesn't make sense.

So I'll suppose we have one set of 1001 numbers. We want to show that there must be at least one pair of numbers in the set, one of which is a multiple of the other.

I would start by thinking what it would take to make a set that does not contain any such pairs. Can it contain 1? Can it contain 2?

If that doesn't help (and I think it will), my next line of thinking would involve the pigeonhole principle, as the problem sounds very much like that. Is that something you have learned?

What ideas do you have?
Click to expand...


Hey frined,
first of all thanks for the help.
Yes, you understand the question, I try with the dove principle 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 :)
 
yossa said:
Hey frined,
first of all thanks for the help.
Yes, you understand the question, I try with the dove principle 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 :)
Click to expand...

Try answering my questions: Can the set contain 1? (Yes or no.) Then, can it contain 2?

If you want to use the pigeonhole principle, please show what you tried. (I am not sure it is useful.)
 
Dr.Peterson said:
Try answering my questions: Can the set contain 1? (Yes or no.) Then, can it contain 2?

If you want to use the pigeonhole principle, please show what you tried. (I am not sure it is useful.)
Click to expand...

hey,
i dont know if its useful....
1=no 2=yes
 
yossa said:
hey,
i dont know if its useful....
1=no 2=yes
Click to expand...

I was actually hoping you would state the reasons for your answers, which are perhaps more important.

We are trying to divide the 2000 numbers into two groups, A being the set of 1001 that we want, and B the set of 999 numbers we discard. Our goal is that no number in A will be a multiple of another.

We now know that 1 is in B, because anything is a multiple of 1, so if 1 were in A, then no other number could be in A!

But what is your reason for saying 2 can be in A? This is more subtle. Note that if 2 is in A, then all other even numbers must be in B. Does this have any implications?
 
Dr.Peterson said:
I was actually hoping you would state the reasons for your answers, which are perhaps more important.

We are trying to divide the 2000 numbers into two groups, A being the set of 1001 that we want, and B the set of 999 numbers we discard. Our goal is that no number in A will be a multiple of another.

We now know that 1 is in B, because anything is a multiple of 1, so if 1 were in A, then no other number could be in A!

But what is your reason for saying 2 can be in A? This is more subtle. Note that if 2 is in A, then all other even numbers must be in B. Does this have any implications?
Click to expand...

A friend really really really thanks for the help,
I managed to solve it and received a confirmation from the teacher :)
 
You must log in or register to reply here.
Top