title: Consider the numbers 1,2,...,1000. Show that among any 501 of them, two numbers exist such that one divides the other one.
body: <p>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.</p>
  
  <p>I divided the selection of any 501 numbers into the following cases:</p>
  
  <p>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.</p>