Discrete Math Quiz: Proof By Contrapositive

What this quiz covers

This quiz focuses on Proof By Contrapositive, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

Question 1

1. If for some $\varepsilon > 0$, no element $s \in S$ satisfies $s > \sup(S) - \varepsilon$, then either $S$ is unbounded or $\sup(S)$ is undefined.
2. If there exists $\varepsilon > 0$ such that for all $s \in S$, $s \leq \sup(S) - \varepsilon$, then $S$ is not bounded above or $\sup(S)$ does not exist. (correct answer)
3. If for all $\varepsilon > 0$, there exists $s \in S$ with $s \leq \sup(S) - \varepsilon$, then $S$ has no supremum or is unbounded above.
4. If some $\varepsilon > 0$ exists where every $s \in S$ has $s < \sup(S) - \varepsilon$, then the bounded nature of $S$ or existence of $\sup(S)$ fails.

Question 2

1. Contrapositive proof is logically stronger than direct proof because it establishes both the original statement and its converse simultaneously through bidirectional reasoning.
2. The contrapositive $\neg Q \rightarrow \neg P$ often provides more concrete or constructive assumptions to work with, especially when $Q$ involves existence statements or complex conditions. (correct answer)
3. The contrapositive approach avoids potential circular reasoning that can occur in direct proofs when the hypothesis and conclusion are closely related conceptually.
4. Contrapositive proof requires fewer logical steps and is computationally more efficient, making it preferable for complex mathematical arguments involving multiple quantifiers.

Question 3

1. The algebraic manipulation $n^2 = 4k^2 = 2(2k^2)$ contains an error because $4k^2$ should equal $2(k^2)$, not $2(2k^2)$.
2. The student failed to explicitly state the contrapositive before beginning the proof, making the logical connection unclear to readers.
3. The proof is actually correct and complete; no significant issues exist with the logical structure or mathematical content presented. (correct answer)
4. The proof assumes $n$ is even but should assume $n^2$ is even, since the contrapositive requires negating the conclusion first.

Question 4

1. The contrapositive is correctly stated, but the proof strategy should focus on showing $p = 2$ when $p$ is even and prime, not showing non-primality.
2. The logical structure is sound, but the student should prove $p$ is composite directly rather than using the contrapositive approach for this theorem.
3. The contrapositive formulation is incorrect; it should be "if $p$ is even, then $p$ is not prime or $p = 2$" to properly handle the compound hypothesis.
4. The reasoning is actually correct and complete; assuming $p$ is even and deriving that $p$ is either composite or equals 2 properly proves the contrapositive. (correct answer)

Question 5

1. Correctly negating the compound conclusion to get "$G$ has no Eulerian path or $G$ has an Eulerian cycle" and handling both cases systematically. (correct answer)
2. Establishing that a graph with no Eulerian path must be disconnected, since this requires deep understanding of graph connectivity theory.
3. Proving that if a graph has an Eulerian cycle, then all vertices must have even degree, which contradicts having exactly two odd-degree vertices.
4. Showing that the number of odd-degree vertices in any graph must be even, making it impossible to have exactly two such vertices.

Question 6

1. Assume at least one of $a$ or $b$ is divisible by 3, then prove $ab$ is divisible by 3 using the fundamental theorem of arithmetic. (correct answer)
2. Assume neither $a$ nor $b$ is divisible by 3, then prove $ab$ is not divisible by 3 by showing $\gcd(ab, 3) = 1$.
3. Assume $ab$ is divisible by 3, then prove at least one of $a$ or $b$ must be divisible by 3 using Euclid's lemma.
4. Assume both $a$ and $b$ are divisible by 3, then prove $ab$ is divisible by 9, which implies divisibility by 3.

Question 7

1. The product $y\sqrt{2}$ would be both rational and irrational simultaneously, which is logically impossible by the definition of rational numbers.
2. The sum $x + y\sqrt{2}$ would be irrational since $y\sqrt{2}$ is irrational and $x$ is rational, contradicting our assumption.
3. Since $y \neq 0$, the expression $x + y\sqrt{2}$ cannot be simplified to a rational form, creating a direct contradiction.
4. We could solve for $\sqrt{2} = \frac{r - x}{y}$ where $r$ is rational, making $\sqrt{2}$ rational, which contradicts the irrationality of $\sqrt{2}$. (correct answer)

Question 8

1. $2^n - 1 = (2^a - 1)(2^b - 1) + (2^a - 1) + (2^b - 1)$, providing a factorization where both factors are greater than 1.
2. $2^n - 1 = 2^{ab} - 1 = (2^a)^b - 1$, and since $x^b - 1 = (x-1)(x^{b-1} + x^{b-2} + \cdots + x + 1)$, we get a non-trivial factorization. (correct answer)
3. $2^n - 1 = 2^{ab} - 1$ can be written as $2^a(2^{b-1} - 1) + (2^a - 1)$, giving us two factors each greater than 1.
4. Since $n = ab$ is composite, $2^n - 1$ inherits the composite property directly through the exponential function's behavior on composite inputs.

Question 9

1. Only remainder 1, proving the contrapositive since $n^2 + n + 1$ is never divisible by 3 when $n$ is not divisible by 3. (correct answer)
2. Only remainder 0, which contradicts our assumption and proves the original statement false.
3. Remainders 1 and 2, but never 0, proving the contrapositive since $n^2 + n + 1$ is never divisible by 3 when $n$ is not divisible by 3.
4. Remainders 0, 1, and 2 are all possible, so the contrapositive method cannot be used for this statement.

Question 10

1. $a^2 + b^2 = 4(m^2 + n^2) + 4(m + n) + 2$, which is always even but never divisible by 4, creating the needed contradiction.
2. $a^2 + b^2$ is even, which means $c^2$ is even, so $c$ is even, contradicting the requirement that $a$, $b$, $c$ are positive integers.
3. $a^2 + b^2 \equiv 2 \pmod{4}$, but any perfect square is congruent to 0 or 1 modulo 4, so $c^2$ cannot equal $a^2 + b^2$. (correct answer)
4. $a^2 + b^2$ yields an irrational sum when $a$ and $b$ are both odd, making it impossible for $c^2$ to be an integer.

Question 11

1. The completeness property of real numbers ensures that if neither $x$ nor $y$ is zero, their product cannot be zero by the density of rationals.
2. The field property that real numbers form an integral domain, meaning the product of two nonzero elements is nonzero, directly contradicting $xy = 0$. (correct answer)
3. The multiplicative inverse property guarantees that if $x \neq 0$ and $y \neq 0$, then $x^{-1}$ and $y^{-1}$ exist, making $xy$ invertible and thus nonzero.
4. The ordering property of real numbers implies that if $x \neq 0$ and $y \neq 0$, then both have definite signs, making their product necessarily nonzero.

Question 12

1. Assume $n$ is odd. Then $n = 2k + 1$ for some integer $k$, so $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. Therefore, if $n$ is odd, then $n^2$ is odd. (correct answer)
2. Assume $n^2$ is odd. Then $n^2 = 2k + 1$ for some integer $k$, so $n = \sqrt{2k + 1}$. Since the square root of an odd number is odd, $n$ is odd.
3. Assume $n$ is even. Then $n = 2k$ for some integer $k$, so $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$, which is even. Therefore, if $n$ is even, then $n^2$ is even.
4. Assume $n^2$ is even and $n$ is odd. This leads to a contradiction since $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$, which is odd, not even.

Question 13

1. Factor $a^3 - b^3$ as $(a-b)(a^2 + ab + b^2)$ and show this leads to $a^2 + ab + b^2 = -2$, which is impossible for real numbers. (correct answer)
2. Conclude that since $a^3 - b^3 = 2(b - a)$ and $a \neq b$, we have shown $f$ is not one-to-one, completing the contrapositive proof.
3. Show that $a^3 - b^3 = 2(b - a)$ implies $a = b$, contradicting the assumption that $a \neq b$, thus proving $f$ is one-to-one.
4. Substitute specific values for $a$ and $b$ to show that no such pair exists where $a \neq b$ and $f(a) = f(b)$.

Question 14

1. We can find sequences approaching $a$ where $f$ takes on arbitrarily large values, making $f$ unbounded near $a$ and thus non-differentiable.
2. The function $f$ has a jump discontinuity at $x = a$, making the difference quotient $\frac{f(a+h) - f(a)}{h}$ undefined as $h \to 0$.
3. There exists $\epsilon > 0$ such that for all $\delta > 0$, there exists $x$ with $|x - a| < \delta$ but $|f(x) - f(a)| \geq \epsilon$, which prevents the derivative limit from existing. (correct answer)
4. The limit $\lim_{x \to a} f(x)$ either does not exist or does not equal $f(a)$, preventing the difference quotient from having a finite limit.

Question 15

1. If $G$ is connected and has no vertices of odd degree, then $G$ has an Eulerian cycle rather than an Eulerian path.
2. If $G$ has an Eulerian path, then $G$ is connected and has exactly two vertices of odd degree.
3. If $G$ is disconnected or has a number of odd-degree vertices other than two, then $G$ does not have an Eulerian path.
4. If $G$ does not have an Eulerian path, then $G$ is disconnected or $G$ does not have exactly two vertices of odd degree. (correct answer)

Question 16

1. Assume $\gcd(a,12) > 1$, then factor 12 as $2^2 \cdot 3$ and show $a$ must share factors with the prime factorization components.
2. Assume $\gcd(a,8) \neq 1$ and $\gcd(a,3) \neq 1$, then prove $\gcd(a,12) \geq \text{lcm}(\gcd(a,8), \gcd(a,3)) > 1$.
3. Assume $\gcd(a,8) > 1$ or $\gcd(a,3) > 1$, then show that $a$ shares a common factor with either 8 or 3, both of which divide 12. (correct answer)
4. Assume both $\gcd(a,8) = 1$ and $\gcd(a,3) = 1$ are false, then use the Chinese Remainder Theorem to establish $\gcd(a,24) > 1$.

Question 17

1. Showing that when $n$ is odd, $n^4 + n^2 + 1 \equiv 3 \pmod{4}$, which implies the expression cannot equal 2.
2. Recognizing that $n^4 + n^2 + 1 = (n^2 + n + 1)(n^2 - n + 1)$ when $n$ is odd, providing a non-trivial factorization. (correct answer)
3. Demonstrating that $n^4 + n^2 + 1 > n^2$ for all positive integers $n$, ensuring the expression is always composite when $n$ is odd.
4. Proving that $n^4 + n^2 + 1$ is always odd regardless of the parity of $n$, so primality depends on other structural properties.

Question 18

1. If $n$ is odd, then $n^3 + 5n$ is odd. Prove by assuming $n = 2k+1$ and showing $n^3 + 5n = 2m+1$ for some integer $m$. (correct answer)
2. If $n$ is odd, then $n^3 + 5n$ is even. Prove by assuming $n = 2k+1$ and showing $n^3 + 5n = 2m$ for some integer $m$.
3. If $n^3 + 5n$ is odd, then $n$ is odd. Prove by assuming $n^3 + 5n = 2k+1$ and deriving that $n$ must be odd.
4. If $n$ is not even, then $n^3 + 5n$ is not even. Prove by contradiction, assuming both $n$ is odd and $n^3 + 5n$ is even.

Question 19

1. Contrapositive proof is logically equivalent to direct proof, while contradiction requires assuming the negation of what you want to prove.
2. Contrapositive proof assumes the negation of the conclusion and derives the negation of the hypothesis, making it logically distinct from both direct proof and contradiction.
3. Contrapositive proof is a special case of proof by contradiction where you assume both the hypothesis and negation of the conclusion simultaneously.
4. Contrapositive proof and proof by contradiction both assume negations, but contrapositive derives a specific conclusion while contradiction seeks any logical inconsistency. (correct answer)

Question 20

1. Assume $x = 3$, substitute to get $9 - 21 + 12 = 0$, conclude $x^2 - 7x + 12 = 0$, therefore the contrapositive holds. (correct answer)
2. Assume $x \neq 3$, factor $x^2 - 7x + 12 = (x-3)(x-4)$, show this equals zero only when $x = 4$, conclude the original statement.
3. Factor $x^2 - 7x + 12 = (x-3)(x-4)$, assume $x = 3$, substitute to show $x^2 - 7x + 12 = 0$, contrapositive proven.
4. Assume $x^2 - 7x + 12 = 0$, solve to get $x = 3$ or $x = 4$, since $x = 3$ is possible, the contrapositive fails.