1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Induction / divisibility problem

  1. Sep 27, 2011 #1
    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/NonDividingSets/index.aspx
    Last edited: Sep 27, 2011
  2. jcsd
  3. Sep 28, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper

    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?
    Last edited: Sep 28, 2011
  4. Sep 28, 2011 #3
    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.
  5. Sep 28, 2011 #4


    User Avatar
    Homework Helper

    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.
  6. Sep 28, 2011 #5


    User Avatar
    Science Advisor
    Homework Helper

    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)"?
    Last edited: Sep 28, 2011
  7. Sep 28, 2011 #6
    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.
  8. Sep 28, 2011 #7
    Wrote the whole proof on paper and it makes sense now. Thank you for your help!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook