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

Question

I came across this question in the book 'Invitation to Discrete Mathematics' by Matousek and Nesetril. I am new to these kinds of problems. I approached to this problem in this way: The two numbers selected among any 501 numbers consist of a divisor and a dividend. A number greater than 500 cannot be a divisor. So we need at least one number in the range 1-500 inclusive. And we will in fact get a number in that range given the fact that we need to select 501 numbers from 1000 numbers.

I divided the selection of any 501 numbers into the following cases:

Case 1- We select all numbers between 501-1000 inclusive and any number between 1-500 inclusive. In this case, the statement is easily provable because all the numbers between 1-500 have at least one dividend in the range 501-1000 and that whole range is selected. Case 2- We select all numbers between 1-500 inclusive and any one number between 501-1000 inclusive. In this case also, the statement is easily provable as there are many pairs in the range 1-500 that serve as divisors and dividends to each other. Case 3- We select some numbers in the range 1-500 and some numbers in the range 501-1000. I am having trouble proving that for some number in the range 1-500,there is a dividend for that selected.

Answer 1

This question may be off-topic for SO, but here's a proof that makes use the pidgeonhole principle:

Each number can be written in the form 2^k(2m+1) where k,m ≥ 0.

Because each number is less than 1001, m must be less than 500.

So since you're choosing 501 numbers, two of the numbers must have the same m value.

These two numbers can be written as 2^k1(2m+1) and 2^k2(2m+1).

Either k1 ≤ k2 or k2 ≤ k1, so without loss of generality, assume k1 ≤ k2.

Then 2^k1(2m+1) divides 2^k2(2m+1), which is what was to be proved.