logic - Consider the numbers 1,2,...,1000. Show that among any 501 of them, two numbers exist such that one divides the other one. -

i came across question in book 'invitation discrete mathematics' matousek , nesetril. new these kinds of problems. approached problem in way: 2 numbers selected among 501 numbers consist of divisor , dividend. number greater 500 cannot divisor. need @ least 1 number in range 1-500 inclusive. , in fact number in range given fact need select 501 numbers 1000 numbers.

i divided selection of 501 numbers following cases:

case 1- select numbers between 501-1000 inclusive , number between 1-500 inclusive. in case, statement provable because numbers between 1-500 have @ least 1 dividend in range 501-1000 , whole range selected. case 2- select numbers between 1-500 inclusive , 1 number between 501-1000 inclusive. in case also, statement provable there many pairs in range 1-500 serve divisors , dividends each other. case 3- select numbers in range 1-500 , numbers in range 501-1000. having trouble proving number in range 1-500,there dividend selected.

this question may off-topic so, here's proof makes use pidgeonhole principle:

each number can written in form 2^k(2m+1) k,m ≥ 0.

because each number less 1001, m must less 500.

so since you're choosing 501 numbers, 2 of numbers must have same m value.

these 2 numbers can written 2^k1(2m+1) , 2^k2(2m+1).

either k1 ≤ k2 or k2 ≤ k1, without loss of generality, assume k1 ≤ k2.

then 2^k1(2m+1) divides 2^k2(2m+1), proved.