Induction / divisibility problemby scumtk Tags: balkaniad, divisibility, induction, number theory, olympiad 

#1
Sep2711, 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 noninductive solution: http://www.mathnerds.com/best/NonDiv...ets/index.aspx 



#2
Sep2811, 12:08 AM

Sci Advisor
HW Helper
Thanks
P: 25,170

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?




#3
Sep2811, 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. 



#4
Sep2811, 02:55 AM

HW Helper
P: 1,373

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. 



#5
Sep2811, 08:32 AM

Sci Advisor
HW Helper
Thanks
P: 25,170





#6
Sep2811, 10:27 AM

P: 4





#7
Sep2811, 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 