# Proofs by contraposition and contradiction

1. Apr 20, 2014

### spaghetti3451

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. Apr 20, 2014

### AlephZero

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?

3. Apr 20, 2014

### spaghetti3451

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?

4. Apr 20, 2014

### AlephZero

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.

5. Apr 21, 2014

### spaghetti3451

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?

6. Apr 21, 2014

### HallsofIvy

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 $a_i$ be the number of points the "$i^{th}$" student received, we must have $a_i< k$ for all i and so $\sum_{i=1}^n a_i< kn$.