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!

Proofs by contraposition and contradiction

  1. Apr 20, 2014 #1
    1. The problem statement, all variables and given/known data

    (a) Prove that if n is an integer and n2 is a multiple of 3, then n is a multiple of 3.
    (b) Consider a class of n students. In an exam, the class average is k points. Prove, using contradiction, that at least one student must have received at least k marks in the exam.

    2. Relevant equations

    3. The attempt at a solution

    (a) I think I've solved the first one correctly. Here's my attempt.
    Assume that n is not a multiple of 3.
    Therefore, n ≠ 3p, where p is an integer.
    Therefore, n2 ≠ 9p2.
    Therefore, n2 ≠ 3(3p2).
    Therefore, n2 is not a multiple of 3.
    Therefore, by contraposition, if n2 is a multiple of 3, then n is a multiple of 3.

    (b) The second one I've made a partial attempt as I could not figure how to proceed. Here's my attempt.

    Assume that class average ≠ k points.
    Therefore, total sum of marks of all students ≠ nk points.
    No idea of how to proceed from here onwards.

    It would be great if you could supply hints on how to carry forward and check my first solution as well.
     
  2. jcsd
  3. Apr 20, 2014 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    That is true, but it doesn't follow that
    You haven't shown that n2 ≠ 3q, for some integer q that is NOT of the form 3p2.

    Try starting from what you are given: n2 is a multiple of 3, and of course n2 is a square.

    Think about what "average" means. If all the students recieved less than k marks, what would the average mark be?
     
  4. Apr 20, 2014 #3
    I have my new proofs.

    a) n2 is a multiple of 3.
    Therefore, n2 = 3p, where p is an integer.
    n2 is a square.
    Therefore, if n2 is to have a factor of 3, it must have an even number of such factors.
    Therefore, p = 3q, where q is an integer.
    Therefore, n2 = 9q.
    Therefore, n = 3√q.
    Therefore, n is a multiple of 3.

    b) Assume that all students received less than k points.
    Therefore, the class average is less than k points.
    But, the class average is k points.
    Therefore, at least one student must have received at least k points in the exam.

    What do you think?
     
  5. Apr 20, 2014 #4

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Both those proofs are basically OK.

    I wouldn't give the first one full marks, because
    is correct, but you didn't explain why it is correct.

    For example if n2 was a multiple of 12 instead of 3, n doesn't have to be a multiple of 12 - it could be 6.
     
  6. Apr 21, 2014 #5
    If n2 were a multiple of 12, then n2 = (22)(32)(k), where k is a constant.

    Therefore, it is okay for n to be equal (2)(3)(√k), i.e. for n to be a multiple of 6.

    The real crux of the issue lies with the fact that 3 is a prime factor, and therefore 3 cannot be decomposed further into smaller factors. Therefore, an odd number of 3's have to exist within k for n2 to exist and for n to be a integer.

    The argument could be written as follows:

    3 is a prime factor. Therefore, k must be a multiple of an odd number of 3's for n to be an integer.
    Therefore, n2 must have an even number of factors of 3.

    How does this look?
     
  7. Apr 21, 2014 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    For (a) a simple proof by contradiction is:
    Suppose n is not a multiple of 3. Then n= 3k+1 or n= 3k+ 2 for some integer k. Now square each of 3n+1 and 3n+ 2.

    For (b), assume, in contradiction to the conclusion, that no student received at least k points. Then, letting [itex]a_i[/itex] be the number of points the "[itex]i^{th}[/itex]" student received, we must have [itex]a_i< k[/itex] for all i and so [itex]\sum_{i=1}^n a_i< kn[/itex].
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proofs by contraposition and contradiction
  1. Contrapositive proof (Replies: 7)

  2. Proof by contradiction (Replies: 6)

  3. Contrapositive proof (Replies: 5)

  4. Proof by contradiction (Replies: 4)

  5. Proof by contradiction (Replies: 5)

Loading...