Answer to Question #19301 in Combinatorics | Number Theory for marcus

Question

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.

Answer 1

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.