Proofs by contraposition and contradiction

[spaghetti3451]

Homework Statement

(a) Prove that if n is an integer and n² 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.

Homework Equations

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, n² ≠ 9p².
Therefore, n² ≠ 3(3p²).
Therefore, n² is not a multiple of 3.
Therefore, by contraposition, if n² 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.

 

[AlephZero]

Assume that n is not a multiple of 3.
Therefore, n ≠ 3p, where p is an integer.
Therefore, n² ≠ 9p².
Therefore, n² ≠ 3(3p²).

That is true, but it doesn't follow that

Therefore, n² is not a multiple of 3.

You haven't shown that n² ≠ 3q, for some integer q that is NOT of the form 3p².

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

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

Think about what "average" means. If all the students received less than k marks, what would the average mark be?

 

[spaghetti3451]

I have my new proofs.

a) n² is a multiple of 3.
Therefore, n² = 3p, where p is an integer.
n² is a square.
Therefore, if n² 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, n² = 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?

 

[AlephZero]

Both those proofs are basically OK.

I wouldn't give the first one full marks, because

Therefore, if n² is to have a factor of 3, it must have an even number of such factors.

is correct, but you didn't explain why it is correct.

For example if n² was a multiple of 12 instead of 3, n doesn't have to be a multiple of 12 - it could be 6.

 

[spaghetti3451]

If n² were a multiple of 12, then n² = (2²)(3²)(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 n² 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, n² must have an even number of factors of 3.

How does this look?

 

[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 [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].