Question #19301

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.

Expert's answer

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.

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.

## Comments

## Leave a comment