I need help proving a proof by contrapositive. (I dont know where to begin)

Question

So I have been working on a homework assignment and I'm just beyond stuck and can't seem to figure out where to start. We are suppose to prove some proofs with either direct proof, proof by contrapositive, proof by contradiciton, or a proof by cases.

The statement I've been trying to prove is If a group of 8 kids have won a total of 65 trophies, then at least one of the 8 kids has won at least 9 trophies.

I identified that I'm suppose to use a proof by contrapositive for this one. And This is what I assumed, Suppose a group of 8 kids have won a total of 65 trophies and one of the 8 kids won 9 trophies.

I don't really understand what the conclusion is and how exactly I'm suppose to solve for this. Any explanation to how to get started would be very much appreciated.

Answer 1

That's not correct. What you should do is to assume that none of them won more that $8$ trophies and to deduce that the $8$ kids together cannot have won $65$ trophies,

Answer 2

Suppose there not exist any kid with more than 8 trophies, then in total we would have not more than $8\cdot 8=64$ trophies < 65.

For a direct proof refer to Pigeonhole principle.

Answer 3

The statement is:

If 8 kids won 65 trophies then at least one kid one at least 9 trophies

Let P="8 kids won 65 trophies together"

Let Q="1 of 8 kids won at least 9 trophies"

You need to prove $P\to Q $.

Or equivalently to prove the contrapositive $\lnot Q\to \lnot P $.

What is $\lnot Q $?

$\lnot Q=$ None of 8 kids won at least 9 trophies = At most, each of 8 kids won 8 trophies

What is $\lnot P $?

Well that's simply $\lnot P =$ the 8 kids didn't win 65 trophies.

So you need to prove:

If 8 kids won at most 8 trophies each then they did not win 65 trophies.

That, in turn should be very easy to prove.

Answer 4

Thanks guys I got the contradiction and the answer! I really appreciate the help you guys gave me. I don't know why it took me a while to figure this out when the answer was literally in my face. But thanks again guys, have a great day!