Discrete Math Prove or disprove that among ANY 501 numbers a

Discrete Math:

Prove or disprove that among ANY 501 numbers are chosen from the numbers 1, 2, …, 1000 there must be at least two numbers such that one divides the other.   

Solution

Dear Student Thank you for using Chegg !! Range given = 1~1000 Let us write each number in the form 2^t(2n+1) where t,n 0. Now since each number is less than 1001, n must be less than 500. While choosing 501 numbers, two of the numbers must have the same m value. These two numbers can be written as 2^t1(2n+1) and 2^t2(2n+1). Either t1 t2 or t2 t1, so without loss of generality, assume t1 t2. Then 2^t1(2n+1) divides 2^t2(2n+1), which is what was to be proved.