Answer to Question #19301 in Combinatorics | Number Theory for marcus
Given n+1 natural numbers, say ,a1,a2,a3,,...,an+1 all less than or equal to 2n, then there exists a pair, say ai and aj with i j, such that ai divides aj.
Let we have m numbers between 1 .. n and k numbers between n+1 .. 2n. m numbers between 1 .. n have at least m multiples among n+1 .. 2n, and they are all different. Since m + k = n +1 and there are only n numbers between n +1.. 2n it is obvious that these two sets (of mulitples and k number from our n+1) intersect.