1

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.

José Carlos Santos
  • 427,504
Josh
  • 21
  • Try a proof by contradiction: what happen if all of each kids won at most 8 trophies? – user296113 Feb 18 '18 at 20:19
  • The contrapositive of the statement “if $p$, then $q$” is the statement “if not $q$, then not $p$.” In math we would write that the contrapositive of “$p \implies q$” is “$\sim q \implies \sim p$.” Based on this, the contrapositive statement you wrote down is wrong. Your statement $p$ is “a group of 8 kids has won 65 trophies” and $q$ is “at least one has won at least 9 trophies.” Based on this, the contrapositive is “if all 8 kids have each won no more than 8, then the group of 8 kids has not won 65 trophies” and this is the statement you will prove if you choose to use contrapositive. – layman Feb 18 '18 at 20:23
  • Contrapositive: Assume all 8 kids have won less than 9 trophies. Show this implies that they did not win a total of 65 trophies. – Air Conditioner Feb 18 '18 at 20:23

4 Answers4

1

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.

fleablood
  • 124,253
1

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!

Josh
  • 21
0

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,

José Carlos Santos
  • 427,504
  • 1
    Ok when I change my assumption to that will I have to change the sentence in terms of p and q? So for the original statement " 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." would it be p -> q. then the assume statement would be notq and notp – Josh Feb 18 '18 at 20:22
  • @Josh What you shoud do is to assume not $q$ and to deduce not $p$. – José Carlos Santos Feb 18 '18 at 20:35
0

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.

user
  • 154,566