Pigeonhole principle problem 4 [duplicate]
$begingroup$
This question already has an answer here:
Elementary number theory in sets
2 answers
If we select $1001$ numbers from the set ${1,2,3,…,2000}$ there will be two numbers selected such that one divides the other. We need to prove this fact by noting that every number in the given set can be expressed in the form $2^k⋅m$ where m is an odd number and using the pigeonhole principle. Thank you.
combinatorics
edited Dec 20 '18 at 21:33
Community♦
1
asked Dec 20 '18 at 21:07
O.JoenO.Joen
13
$endgroup$
marked as duplicate by greedoid, KReiser, Leucippus, Lord Shark the Unknown, Saad Dec 21 '18 at 8:29
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Elementary number theory in sets
2 answers
If we select $1001$ numbers from the set ${1,2,3,…,2000}$ there will be two numbers selected such that one divides the other. We need to prove this fact by noting that every number in the given set can be expressed in the form $2^k⋅m$ where m is an odd number and using the pigeonhole principle. Thank you.
combinatorics
edited Dec 20 '18 at 21:33
Community♦
1
asked Dec 20 '18 at 21:07
O.JoenO.Joen
13
$endgroup$
marked as duplicate by greedoid, KReiser, Leucippus, Lord Shark the Unknown, Saad Dec 21 '18 at 8:29
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
Seems like a good hint. To add a little to it, how many possibilities are there for $m$?
$endgroup$
– lulu
Dec 20 '18 at 21:10
1
$begingroup$
What have you tried?
$endgroup$
– Tito Eliatron
Dec 20 '18 at 21:13
add a comment |
$begingroup$
This question already has an answer here:
Elementary number theory in sets
2 answers
If we select $1001$ numbers from the set ${1,2,3,…,2000}$ there will be two numbers selected such that one divides the other. We need to prove this fact by noting that every number in the given set can be expressed in the form $2^k⋅m$ where m is an odd number and using the pigeonhole principle. Thank you.
combinatorics
edited Dec 20 '18 at 21:33
Community♦
1
asked Dec 20 '18 at 21:07
O.JoenO.Joen
13
$endgroup$
This question already has an answer here:
Elementary number theory in sets
2 answers
If we select $1001$ numbers from the set ${1,2,3,…,2000}$ there will be two numbers selected such that one divides the other. We need to prove this fact by noting that every number in the given set can be expressed in the form $2^k⋅m$ where m is an odd number and using the pigeonhole principle. Thank you.
This question already has an answer here:
Elementary number theory in sets
2 answers
combinatorics
combinatorics
edited Dec 20 '18 at 21:33
Community♦
1
asked Dec 20 '18 at 21:07
O.JoenO.Joen
13
edited Dec 20 '18 at 21:33
Community♦
1
asked Dec 20 '18 at 21:07
O.JoenO.Joen
13
edited Dec 20 '18 at 21:33
Community♦
1
edited Dec 20 '18 at 21:33
Community♦
1
edited Dec 20 '18 at 21:33
Community♦
1
1
asked Dec 20 '18 at 21:07
O.JoenO.Joen
13
asked Dec 20 '18 at 21:07
O.JoenO.Joen
13
asked Dec 20 '18 at 21:07
O.JoenO.Joen
13
13
marked as duplicate by greedoid, KReiser, Leucippus, Lord Shark the Unknown, Saad Dec 21 '18 at 8:29
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by greedoid, KReiser, Leucippus, Lord Shark the Unknown, Saad Dec 21 '18 at 8:29
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
Seems like a good hint. To add a little to it, how many possibilities are there for $m$?
$endgroup$
– lulu
Dec 20 '18 at 21:10
1
$begingroup$
What have you tried?
$endgroup$
– Tito Eliatron
Dec 20 '18 at 21:13
add a comment |
1
$begingroup$
Seems like a good hint. To add a little to it, how many possibilities are there for $m$?
$endgroup$
– lulu
Dec 20 '18 at 21:10
1
$begingroup$
What have you tried?
$endgroup$
– Tito Eliatron
Dec 20 '18 at 21:13
1
1
$begingroup$
Seems like a good hint. To add a little to it, how many possibilities are there for $m$?
$endgroup$
– lulu
Dec 20 '18 at 21:10
$begingroup$
Seems like a good hint. To add a little to it, how many possibilities are there for $m$?
$endgroup$
– lulu
Dec 20 '18 at 21:10
1
1
$begingroup$
What have you tried?
$endgroup$
– Tito Eliatron
Dec 20 '18 at 21:13
$begingroup$
What have you tried?
$endgroup$
– Tito Eliatron
Dec 20 '18 at 21:13
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are only $1000$ possibilities for what $m$ can be, so if you select $1001$ numbers, among them will be two numbers $2^k m$ and $2^{k'} m'$ such that $m=m'$. Can you conclude from here?
answered Dec 20 '18 at 21:12
angryavianangryavian
40.6k23380
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are only $1000$ possibilities for what $m$ can be, so if you select $1001$ numbers, among them will be two numbers $2^k m$ and $2^{k'} m'$ such that $m=m'$. Can you conclude from here?
answered Dec 20 '18 at 21:12
angryavianangryavian
40.6k23380
$endgroup$
add a comment |
$begingroup$
There are only $1000$ possibilities for what $m$ can be, so if you select $1001$ numbers, among them will be two numbers $2^k m$ and $2^{k'} m'$ such that $m=m'$. Can you conclude from here?
answered Dec 20 '18 at 21:12
angryavianangryavian
40.6k23380
$endgroup$
add a comment |
$begingroup$
There are only $1000$ possibilities for what $m$ can be, so if you select $1001$ numbers, among them will be two numbers $2^k m$ and $2^{k'} m'$ such that $m=m'$. Can you conclude from here?
answered Dec 20 '18 at 21:12
angryavianangryavian
40.6k23380
$endgroup$
There are only $1000$ possibilities for what $m$ can be, so if you select $1001$ numbers, among them will be two numbers $2^k m$ and $2^{k'} m'$ such that $m=m'$. Can you conclude from here?
answered Dec 20 '18 at 21:12
angryavianangryavian
40.6k23380
answered Dec 20 '18 at 21:12
angryavianangryavian
40.6k23380
answered Dec 20 '18 at 21:12
angryavianangryavian
40.6k23380
answered Dec 20 '18 at 21:12
angryavianangryavian
40.6k23380
40.6k23380
add a comment |
add a comment |
1
$begingroup$
Seems like a good hint. To add a little to it, how many possibilities are there for $m$?
$endgroup$
– lulu
Dec 20 '18 at 21:10
1
$begingroup$
What have you tried?
$endgroup$
– Tito Eliatron
Dec 20 '18 at 21:13