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

    Dick

    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

    verty

    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

    Dick

    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