Register to reply

Induction / divisibility problem

Share this thread:
scumtk
#1
Sep27-11, 08:36 PM
P: 4
1. The problem statement, all variables and given/known data

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/NonDiv...ets/index.aspx
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
Dick
#2
Sep28-11, 12:08 AM
Sci Advisor
HW Helper
Thanks
P: 25,251
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
#3
Sep28-11, 01:25 AM
P: 4
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
#4
Sep28-11, 02:55 AM
HW Helper
P: 1,731
Induction / divisibility problem

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
#5
Sep28-11, 08:32 AM
Sci Advisor
HW Helper
Thanks
P: 25,251
Quote Quote by scumtk View Post
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
#6
Sep28-11, 10:27 AM
P: 4
Quote Quote by Dick View Post
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
#7
Sep28-11, 04:33 PM
P: 4
Wrote the whole proof on paper and it makes sense now. Thank you for your help!


Register to reply

Related Discussions
Proof by Induction - Divisibility Proofs Precalculus Mathematics Homework 3
Prove by induction divisibility question Precalculus Mathematics Homework 2
Proof by mathematical Induction: Divisibility Math & Science Software 3
Mathmatical Induction Problem (Divisibility) Precalculus Mathematics Homework 2
Divisibility problem cant use module just induction Linear & Abstract Algebra 8