Induction / divisibility problem

[scumtk]

Homework Statement

Prove by induction that no matter how one chooses a set of n+1 positive integers from the first 2n positive integers, one integer in the set divides another integer in the set.

2. The attempt at a solution

Tried direct induction. Base case easy to prove. P(n+1) is with n+2 integers from the first 2n+2. Suppose that at most one is 2n+1 or 2n+2 => there are at least n+1 to be chosen from the first 2n integers (which P(n) guarantees will contain two that divide each other). Therefore, I reduced the problem to "n integers from the first 2n, plus 2n+1 and 2n+2".

So now I have to prove that: given any set of n integers from 1 to 2n (EDIT: such that none divides another in the set), one of them divides 2n+1 OR 2n+2. I am clueless from here on. Maybe my whole approach is misguided? I have to emphasize that using induction is a necessity.

Thank you in advance for your help!

EDIT 2: I know the solution that does not require induction, with the bins based on 2^k * (2i+1) factorization of all the numbers there, and I can use that in the place where I am stuck, but that is extremely artificial because the same argument that I would use in the inductive step could be used completely not modified in the initial problem, so the induction would be superfluous. I am looking for a "real" inductive solution. Here's a link to non-inductive solution: http://www.mathnerds.com/best/NonDividingSets/index.aspx

 

[Dick]

Your thinking is pretty clear on this. Ok, so you've got n elements of [1,2n] that don't divide each other. Assume the opposite. That they don't divide 2n+2=2*(n+1). That means they don't divide (n+1). Does (n+1) divide anything in [1,2n]? What's wrong with this picture?

 

[scumtk]

I'm sorry, I don't see how that helps.

P: given any set of n integers from 1 to 2n such that none divides another in the set
Q: one of them divides 2n+1 OR 2n+2

You suggested a proof by contradiction, Q' => P'.

Q': given any set of n integers from 1 to 2n such that none divides 2n+1 nor 2n+2
P': one of them divides another in the set

I don't understand your argument because it seems to me that you suggest that 2 and n+1 cannot be in the set. That doesn't tell me that given any set with that property Q' (i.e. any set without 2 and n+1 necessarily but not sufficiently), there will be one integer that divides another number in the set.

Maybe you could elaborate a bit? Thanks for the fast reply.

 

[verty]

Dick has answered your question.

If you assume that for some 2n, no n+1 positive integers below it are linearly independent, then that can never happen. So that is the contradiction you want to show. Try to deduce that there are n+1 linearly independent numbers below 2n.

 

[Dick]

I'm sorry, I don't see how that helps.

P: given any set of n integers from 1 to 2n such that none divides another in the set
Q: one of them divides 2n+1 OR 2n+2

You suggested a proof by contradiction, Q' => P'.

Q': given any set of n integers from 1 to 2n such that none divides 2n+1 nor 2n+2
P': one of them divides another in the set

I don't understand your argument because it seems to me that you suggest that 2 and n+1 cannot be in the set. That doesn't tell me that given any set with that property Q' (i.e. any set without 2 and n+1 necessarily but not sufficiently), there will be one integer that divides another number in the set.

Maybe you could elaborate a bit? Thanks for the fast reply.

Maybe I didn't say it well. If none of the n numbers in [1,2n] divides 2*(n+1), then none of those numbers divides (n+1). Now you can add (n+1) to the list of n numbers. Then use the induction hypothesis. Don't you get a contradiction with "none of those numbers divides (n+1)"?

 

[scumtk]

Maybe I didn't say it well. If none of the n numbers in [1,2n] divides 2*(n+1), then none of those numbers divides (n+1). Now you can add (n+1) to the list of n numbers. Then use the induction hypothesis. Don't you get a contradiction with "none of those numbers divides (n+1)"?

Let me see if I got this. I would basically be proving that none of the n numbers divides n+1, n+1 divides neither of the numbers, but when taken together with them the IH shows that one number divides another. Since n+1 cannot be involved, it means this happened before the insertion of n+1. Q' => P' proven.

 

[scumtk]

Wrote the whole proof on paper and it makes sense now. Thank you for your help!