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
NASA team lays plans to observe new worlds
IHEP in China has ambitions for Higgs factory
Spinach could lead to alternative energy more powerful than Popeye
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,716
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