I am looking for some much needed help please with one question on the Computer Science Path, Math for Computer Science Exam, Part 2.
The question states: Fill in the blanks to match each statement with the type of proof strategy that should be used to prove, or disprove, that statement.
- Prove that all the set of numbers from 1 to 10 are less than 11.
Proof Strategy: ________ - Prove that all numbers less then 5 are odd.
Proof Strategy: ________ - Prove that, if a graph has “n” vertices, it has “n-1” edges.
Proof Strategy: ________
The options are: Contrapositive, Counterexample, Induction, Direct, Existence, Exhaustion (Once an option is selected, it cannot be used elsewhere in the response).
To solve the question, I have used the Article - Proofs: Methods and Strategies and the Article – Proofs: Problem Set to guide my reasoning.
My response follows the format that was provided in the Articles and Problem Sets:
-
Response: Exhaustion
Given Statement: Prove that all the set of numbers from 1 to 10 are less than 11.
From the Article, the definition of the Proof by Exhaustion Method states that any statement that suggests the existence of some property for every number can be proven by showing directly that every number has that property.
Given the set of numbers S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, we have:
1 is less than every number is the set S.
10 is greater than every number in the set S.
10 is less than 11.
Therefore, every number in the set of numbers from 1 to 10 are less than 11 and we have proved the statement. -
Response: Direct
Given Statement: Prove that all numbers less then 5 are odd.
From the Article, the definition of the Direct Method states that most simple statements can be proven directly. No keyword really “gives away” the impression that this method of proof is needed.
The number 4 is less than 5. The property for an even number is that it is divisible by two, and leaves the remainder 0. The number 4 is an even number.
Therefore, this uses the Direct Method to disprove our given statement. -
Response: Counterexample
Given Statement: Prove that, if a graph has “n” vertices, it has “n-1” edges.
From the Article, the definition of the Proof by Counterexample Method states: any statement that suggests every number has a certain property can be disproven if you can provide a number that does not have that property.
Without diving too deeply into graph theory, it is simple to see that the statement is false.
The definition of a Null Graph is a graph having one (or more) vertices and no edges. For this counterexample, we can choose a Null Graph with 3 vertices and no edges.
Therefore, this uses the Proof by Counterexample Method to disprove our given statement.
I would really appreciate some help to identify where I’ve gone wrong. My struggle has become totally unproductive. I’ve tried several other methods over multiple attempts without success. Each time I’ve written a proof that I assume to be “the proof strategy that should be used,” as the exam question states.
My Attempt #1: Exhaustion, Direct, Counterexample
My Attempt #2: Exhaustion, Counterexample, Direct
My Attempt #3: Direct, Counterexample, Existence
All of these attempts are incorrect. There are only two questions in Part 2 of the Exam, and I’ve answered the other question correctly. Until I get this question correct, I cannot pass this part of the exam.
Thanks in advance for your time.