Choosing the Right n Numbers from {1,2,3,...,2n}

[cragar]

Homework Statement

Prove that if one chooses more than n numbers from the set {1,2,3, . . . ,2n}, then one number is a multiple of another. Can this be avoided with exactly n numbers?

The Attempt at a Solution

If we pick the top half of the set n+1 up to 2n we will have n numbers that are not multiples of each other. the smallest multiple of n+1 is 2(n+1) but this is outside the set. and there are n numbers from n+1 to 2n. if i pick numbers below n+1 then their double would be in the top half of the set. so the best way to pick them is the top half of the set from n+1 to 2n

 

[haruspex]

Homework Statement

Prove that if one chooses more than n numbers from the set {1,2,3, . . . ,2n}, then one number is a multiple of another. Can this be avoided with exactly n numbers?

The Attempt at a Solution

If we pick the top half of the set n+1 up to 2n we will have n numbers that are not multiples of each other. the smallest multiple of n+1 is 2(n+1) but this is outside the set. and there are n numbers from n+1 to 2n. if i pick numbers below n+1 then their double would be in the top half of the set. so the best way to pick them is the top half of the set from n+1 to 2n

That certainly is a way to pick n without picking one that divides another. What about the proof that you cannot pick n+1?