Discrete Math Quiz: Proof By Cases

20 questions · exam conditions

0:00

Proof By CasesQuestion 1 of 20

A proof by cases is used to establish: "For integers $a, b, c$ with $a^2 + b^2 = c^2$ , at least one of $a, b, c$ is divisible by 4." The proof considers cases based on the remainders of $a$ and $b$ when divided by 4. Which combination of cases leads to the conclusion that $c$ must be divisible by 4?

When both

a \equiv 2 \pmod{4}

and

b \equiv 2 \pmod{4}

, since then

c^2 \equiv 8 \equiv 0 \pmod{4}

, forcing

c \equiv 0 \pmod{4}

When

a \equiv 1 \pmod{4}

and

b \equiv 3 \pmod{4}

, since then

c^2 \equiv 1 + 9 \equiv 2 \pmod{4}

, which requires

c \equiv 0 \pmod{4}

When both

a \equiv 2 \pmod{4}

and

b \equiv 2 \pmod{4}

, since then

c^2 \equiv 4 + 4 \equiv 0 \pmod{8}

, which forces

c

to be divisible by 4

When

a \equiv 0 \pmod{4}

and

b \not\equiv 0 \pmod{4}

, since the constraint

a^2 + b^2 = c^2

forces

c^2 \equiv b^2 \pmod{4}

, making

c \equiv 0 \pmod{4}

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Proof By Cases

Practice Proof By Cases in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Proof By Cases, 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.

All questions

Question 1

When both $a \equiv 2 \pmod{4}$ and $b \equiv 2 \pmod{4}$ , since then $c^2 \equiv 8 \equiv 0 \pmod{4}$ , forcing $c \equiv 0 \pmod{4}$
When $a \equiv 1 \pmod{4}$ and $b \equiv 3 \pmod{4}$ , since then $c^2 \equiv 1 + 9 \equiv 2 \pmod{4}$ , which requires $c \equiv 0 \pmod{4}$
When both $a \equiv 2 \pmod{4}$ and $b \equiv 2 \pmod{4}$ , since then $c^2 \equiv 4 + 4 \equiv 0 \pmod{8}$ , which forces $c$ to be divisible by 4 (correct answer)
When $a \equiv 0 \pmod{4}$ and $b \not\equiv 0 \pmod{4}$ , since the constraint $a^2 + b^2 = c^2$ forces $c^2 \equiv b^2 \pmod{4}$ , making $c \equiv 0 \pmod{4}$

Explanation: When

a \equiv 2 \pmod{4}

and

b \equiv 2 \pmod{4}

, we have

a^2 \equiv 4 \equiv 0 \pmod{4}

and

b^2 \equiv 4 \equiv 0 \pmod{4}

. More precisely,

a^2 \equiv 0 \pmod{8}

and

b^2 \equiv 0 \pmod{8}

when

a, b \equiv 2 \pmod{4}

, so

c^2 = a^2 + b^2 \equiv 0 \pmod{8}

. This forces

c

to be even, and since

c^2 \equiv 0 \pmod{8}

, we must have

c \equiv 0 \pmod{4}

. Choice A has an arithmetic error. Choice B is impossible since no perfect square is congruent to 2 modulo 4. Choice D incorrectly analyzes the modular arithmetic.

Question 2

In proving "every integer $n \geq 12$ can be expressed as $4a + 5b$ where $a, b$ are non-negative integers," a student uses strong induction with proof by cases in the inductive step. For $n = k+1$ where $k \geq 12$ , the student considers cases based on the remainder when $k+1$ is divided by 4. Which case requires invoking the inductive hypothesis?

Case: $k+1 \equiv 0 \pmod{4}$ , because this allows direct construction as $k+1 = 4 \cdot \frac{k+1}{4} + 5 \cdot 0$ .
Case: $k+1 \equiv 1 \pmod{4}$ , because this requires using the hypothesis for $k+1-5 = k-4$ to handle the remainder. (correct answer)
Case: $k+1 \equiv 2 \pmod{4}$ , because this requires using the hypothesis for $k+1-10 = k-9$ to eliminate two fives.
Case: $k+1 \equiv 3 \pmod{4}$ , because this requires using the hypothesis for $k+1-15 = k-14$ to handle three fives.

Explanation: When k+1 ≡ 1 (mod 4), we cannot express k+1 directly as 4a since it's not divisible by 4. However, k+1-5 = k-4 ≡ 0 (mod 4) and k-4 ≥ 8 (since k ≥ 12), so we can apply the inductive hypothesis to k-4 = 4a + 5b, giving k+1 = 4a + 5(b+1). Choice A allows direct construction, Choice C has k-9 which might be less than 12, and Choice D has k-14 which could be negative.

Question 3

Consider the statement: "For any integer $n \geq 2$ , either $n$ is prime or $n$ has a prime divisor $p \leq \sqrt{n}$ ." A student plans to prove this by cases, dividing based on whether $n$ is prime or composite. What is the primary weakness in this approach?

The case division creates a circular argument since determining whether $n$ is prime or composite requires the very result being proved. (correct answer)
The case division is incomplete because it doesn't separately handle the case where $n$ is a perfect square versus non-perfect square.
The case division is too broad and should instead focus on specific forms like $n = p^k$ where $p$ is prime and $k \geq 1$ .
The case division is logically sound, but computationally inefficient compared to direct construction methods for finding prime divisors.

Explanation: The proposed case division (prime vs. composite) is circular because to determine which case applies, we would need to already know whether n is prime—which is essentially what the statement is designed to help us determine efficiently. A better approach would use contradiction or direct construction. Choice B suggests an irrelevant distinction, Choice C proposes an overly complex division, and Choice D incorrectly accepts the circular logic as sound.

Question 4

In proving "for any positive integer $n$ , $\left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n+1}{2} \right\rfloor = n$ " by cases on the parity of $n$ , a student analyzes Case 1 ( $n$ even) and Case 2 ( $n$ odd). In Case 2, when $n = 2k + 1$ for some integer $k \geq 0$ , what are the values of the two floor expressions?

$\left\lfloor \frac{2k+1}{2} \right\rfloor = \frac{2k+1}{2}$ and $\left\lfloor \frac{2k+2}{2} \right\rfloor = k+1$ , but the first expression is not an integer.
$\left\lfloor \frac{2k+1}{2} \right\rfloor = k+1$ and $\left\lfloor \frac{2k+2}{2} \right\rfloor = k+1$ , giving sum $2k+2 \neq n$ .
$\left\lfloor \frac{2k+1}{2} \right\rfloor = k$ and $\left\lfloor \frac{2k+2}{2} \right\rfloor = k$ , giving sum $2k \neq n$ .
$\left\lfloor \frac{2k+1}{2} \right\rfloor = k$ and $\left\lfloor \frac{2k+2}{2} \right\rfloor = k+1$ , giving sum $2k+1 = n$ . (correct answer)

Explanation: When proving statements involving floor functions, case analysis based on parity (even vs. odd) is essential because floor functions behave differently depending on whether the input is an integer or has a fractional part. For Case 2 where

n = 2k + 1

(odd), you need to evaluate

\left\lfloor \frac{2k+1}{2} \right\rfloor + \left\lfloor \frac{(2k+1)+1}{2} \right\rfloor = \left\lfloor \frac{2k+1}{2} \right\rfloor + \left\lfloor \frac{2k+2}{2} \right\rfloor

. For the first term:

\frac{2k+1}{2} = k + \frac{1}{2}

, which is not an integer. The floor function gives us the greatest integer less than or equal to this value, so

\left\lfloor k + \frac{1}{2} \right\rfloor = k

. For the second term:

\frac{2k+2}{2} = k+1

, which is exactly an integer. Therefore

\left\lfloor k+1 \right\rfloor = k+1

. The sum is

k + (k+1) = 2k+1 = n

, confirming our formula works for odd

n

. This matches answer choice D. Answer A incorrectly states that

\left\lfloor \frac{2k+1}{2} \right\rfloor = \frac{2k+1}{2}

, but the floor of a non-integer cannot equal that non-integer. Answer B incorrectly claims

\left\lfloor \frac{2k+1}{2} \right\rfloor = k+1

, which would mean the floor of

k + \frac{1}{2}

rounds up rather than down. Answer C gets the second floor value wrong, stating

\left\lfloor k+1 \right\rfloor = k

instead of

k+1

. Remember: the floor function always rounds down to the nearest integer, never up. When the input is already an integer, the floor function leaves it unchanged.

Question 5

Consider the statement: "For all real numbers $x$ , $x^3 - x \geq -\frac{2\sqrt{3}}{9}$ ." A proof by cases analyzes the critical points of $f(x) = x^3 - x$ . After finding $f'(x) = 3x^2 - 1$ , what case division correctly identifies all regions for monotonicity analysis?

Case 1: $x < -\frac{\sqrt{3}}{3}$ ; Case 2: $-\frac{\sqrt{3}}{3} < x < \frac{\sqrt{3}}{3}$ ; Case 3: $x > \frac{\sqrt{3}}{3}$ (correct answer)
Case 1: $x < -1$ ; Case 2: $-1 < x < 0$ ; Case 3: $0 < x < 1$ ; Case 4: $x > 1$
Case 1: $x \leq -\frac{1}{\sqrt{3}}$ ; Case 2: $-\frac{1}{\sqrt{3}} \leq x \leq \frac{1}{\sqrt{3}}$ ; Case 3: $x \geq \frac{1}{\sqrt{3}}$
Case 1: $x < 0$ ; Case 2: $x = 0$ ; Case 3: $x > 0$

Explanation: Setting f'(x) = 3x² - 1 = 0 gives x² = 1/3, so x = ±√3/3 = ±1/√3. These critical points divide the domain into three intervals where f'(x) has consistent sign: f'(x) > 0 for x < -√3/3 and x > √3/3 (function increasing), and f'(x) < 0 for -√3/3 < x < √3/3 (function decreasing). Choice B uses incorrect critical points, Choice C uses the correct points but with unnecessary boundary inclusions, and Choice D ignores the actual critical points.

Question 6

A proof by cases for the statement " $n^4 - n^2$ is divisible by 12 for all integers $n$ " requires showing divisibility by both 3 and 4. If a student chooses to prove divisibility by 4 using cases based on $n \pmod{4}$ , which case requires the most careful analysis?

Case: $n \equiv 0 \pmod{4}$ , because the fourth power grows rapidly and may cause computational overflow issues.
Case: $n \equiv 1 \pmod{4}$ , because odd residues often lead to more complex algebraic manipulations than even residues.
Case: $n \equiv 2 \pmod{4}$ , because this requires showing that $16k^4 + 32k^3 + 20k^2 - 4k$ is divisible by 4. (correct answer)
Case: $n \equiv 3 \pmod{4}$ , because the resulting expression involves the most terms after expansion and factoring.

Explanation: For n ≡ 2 (mod 4), we have n = 4k + 2, so n⁴ - n² = (4k + 2)⁴ - (4k + 2)². The expansion yields multiple terms, and careful factoring is needed to show divisibility by 4. The other cases are more straightforward: Case A gives immediate divisibility, while Cases B and D, though requiring algebra, follow more standard patterns. Case C requires the most detailed algebraic manipulation to demonstrate the divisibility property.

Question 7

A student proves that " $\sqrt{2}$ is irrational" using proof by cases on the parity of integers $p$ and $q$ in the fraction $\frac{p}{q}$ . The student considers four cases: (even, even), (even, odd), (odd, even), and (odd, odd). Which case analysis contains a fundamental error?

Case (even, even): This case should be excluded from consideration because it violates the assumption that $\gcd(p,q) = 1$ . (correct answer)
Case (even, odd): The algebra becomes intractable when substituting $p = 2k$ into the equation $p^2 = 2q^2$ .
Case (odd, even): This case leads to a contradiction too quickly, suggesting an error in the logical setup.
Case (odd, odd): This case cannot yield a contradiction, indicating that the proof method is fundamentally flawed.

Explanation: In the standard proof that √2 is irrational, we assume √2 = p/q where gcd(p,q) = 1 (fraction in lowest terms). The case (even, even) violates this assumption since both p and q would share the common factor 2. The correct approach shows that cases (even, odd) and (odd, even) both lead to contradictions from p² = 2q². Choice B is wrong since this case is algebraically straightforward, Choice C misunderstands the contradiction mechanism, and Choice D is incorrect as this case does lead to contradiction.

Question 8

To prove "if $n$ is an odd integer, then $8$ divides $n^2 - 1$ ," a student uses cases based on $n \pmod{8}$ . Since $n$ is odd, only four cases need consideration. If the student finds that three cases work correctly but one case seems to fail, which case most likely contains the computational error?

Case: $n \equiv 1 \pmod{8}$ , because $n^2 - 1 \equiv 0 \pmod{8}$ requires careful handling of the identity element.
Case: $n \equiv 3 \pmod{8}$ , because $n^2 - 1 \equiv 8 \pmod{8}$ involves higher-order terms in the expansion.
Case: $n \equiv 5 \pmod{8}$ , because $n^2 - 1 \equiv 24 \pmod{8}$ and reducing $24$ modulo $8$ often leads to arithmetic errors. (correct answer)
Case: $n \equiv 7 \pmod{8}$ , because $n^2 - 1 \equiv 48 \pmod{8}$ and students commonly miscalculate $7^2$ as $47$ instead of $49$ .

Explanation: For n ≡ 5 (mod 8): n² - 1 ≡ 5² - 1 ≡ 25 - 1 ≡ 24 ≡ 0 (mod 8). The error likely occurs in reducing 24 mod 8, where students might incorrectly compute 24 ÷ 8 = 3 remainder 0, but write the remainder as 3, or make similar arithmetic mistakes with the larger intermediate values. The other cases involve smaller intermediate calculations that are less error-prone: Case A gives 0 directly, Case B gives 8 ≡ 0, and Case D gives 48 ≡ 0.

Question 9

Consider proving "if $n$ is an integer and $3n + 2$ is even, then $n$ is even" by contrapositive using proof by cases. The contrapositive statement is "if $n$ is odd, then $3n + 2$ is odd." When $n$ is odd, we can write $n = 2k + 1$ . What does the case analysis reveal about $3n + 2$ ?

$3n + 2 = 3(2k + 1) + 2 = 6k + 5 = 2(3k + 2) + 1$ , but this requires further case analysis on the parity of $k$ .
$3n + 2 = 3(2k + 1) + 2 = 6k + 5 = 2(3k + 3) - 1$ , which is even, contradicting the contrapositive approach.
$3n + 2 = 3(2k + 1) + 2 = 6k + 3 + 2 = 6k + 5$ , which could be even or odd depending on $k$ .
$3n + 2 = 3(2k + 1) + 2 = 6k + 5 = 2(3k + 2) + 1$ , which is odd, proving the contrapositive. (correct answer)

Explanation: When you encounter a proof by contrapositive, you're proving that "if P then Q" by instead proving "if not Q then not P." Here, we're showing that if

n

is odd, then

3n + 2

must be odd. Since

n

is odd, we can write

n = 2k + 1

for some integer

k

. Let's substitute this into

3n + 2

3n + 2 = 3(2k + 1) + 2 = 6k + 3 + 2 = 6k + 5

Now we need to determine the parity of

6k + 5

. We can rewrite this as:

6k + 5 = 6k + 4 + 1 = 2(3k + 2) + 1

Since

2(3k + 2)

is always even (it's 2 times an integer), adding 1 makes the entire expression odd. This proves our contrapositive statement. Option A correctly calculates

2(3k + 2) + 1

but incorrectly claims we need further case analysis on

k

's parity. We don't—the expression is odd regardless of

k

. Option B makes an algebraic error, writing

6k + 5 = 2(3k + 3) - 1

, which gives

6k + 6 - 1 = 6k + 5

. While the arithmetic works out, they incorrectly conclude this makes the expression even. Option C stops at

6k + 5

without recognizing that we can definitively determine its parity by factoring out the even part. Option D correctly performs all calculations and recognizes that

2(3k + 2) + 1

is definitively odd, completing the contrapositive proof. Study tip: In parity proofs, always try to express your result in the form

2(\text{integer}) + 1

(odd) or

2(\text{integer})

(even) to make the conclusion clear.

Question 10

A student attempts to prove that "if $n$ is an integer, then $n^2 + n + 1$ is odd" using proof by cases. The student considers Case 1: $n$ is even, and Case 2: $n$ is odd. In Case 1, the student writes $n = 2k$ and concludes $n^2 + n + 1 = 4k^2 + 2k + 1$ , which is odd. What error, if any, occurs in the Case 2 analysis?

No error occurs; the case division is complete and both cases lead to the correct conclusion that the expression is always odd. (correct answer)
The student fails to substitute $n = 2k + 1$ properly, leading to an incorrect algebraic manipulation in the odd case.
The student correctly handles both cases, but the original statement being proved is actually false for some integer values.
The case division is insufficient because it doesn't account for $n = 0$ , which requires separate consideration in number theory proofs.

Explanation: The proof approach is correct. For Case 2 (n odd): n = 2k+1, so n² + n + 1 = (2k+1)² + (2k+1) + 1 = 4k² + 4k + 1 + 2k + 1 + 1 = 4k² + 6k + 3 = 2(2k² + 3k + 1) + 1, which is odd. The case division is complete and sufficient. Choice B suggests an error that doesn't exist, Choice C is incorrect since the statement is true, and Choice D is wrong since n = 0 is covered in the even case.

Question 11

A student proves that "if $x$ and $y$ are real numbers with $xy > 0$ , then $x$ and $y$ have the same sign" using proof by cases based on the signs of $x$ and $y$ . The student considers four cases: ( $+,+$ ), ( $+,-$ ), ( $-,+$ ), and ( $-,-$ ). What is the key insight that makes this proof by cases work?

The case division is redundant since the hypothesis $xy > 0$ immediately implies the conclusion without case analysis.
All four cases must be shown to satisfy $xy > 0$ individually, then the conclusion follows from exhaustive verification.
Cases ( $+,-$ ) and ( $-,+$ ) require special handling because the product $xy$ approaches zero in these scenarios.
Cases ( $+,+$ ) and ( $-,-$ ) satisfy $xy > 0$ , while cases ( $+,-$ ) and ( $-,+$ ) give $xy < 0$ , contradicting the hypothesis. (correct answer)

Explanation: When you encounter a proof by cases involving conditional statements, you need to understand how the hypothesis constrains which cases are actually possible. In this proof, the key insight is recognizing that not all four sign combinations are consistent with the given hypothesis

xy > 0

. Let's analyze each case systematically:

Case ( $+,+$ ): If both $x > 0$ and $y > 0$ , then $xy > 0$ . This satisfies our hypothesis.
Case ( $-,-$ ): If both $x < 0$ and $y < 0$ , then $xy > 0$ . This also satisfies our hypothesis.
Case ( $+,-$ ): If $x > 0$ and $y < 0$ , then $xy < 0$ . This contradicts our hypothesis $xy > 0$ .
Case ( $-,+$ ): If $x < 0$ and $y > 0$ , then $xy < 0$ . This also contradicts our hypothesis.

The proof works because cases (

+,-

) and (

-,+

) are impossible given the hypothesis, leaving only cases where

x

and

y

have the same sign. This makes answer D correct. Answer A is wrong because the case analysis actually illuminates why the statement is true. Answer B misunderstands the logic—we don't need all cases to satisfy

xy > 0

; rather, we use the hypothesis to eliminate impossible cases. Answer C incorrectly suggests the product "approaches zero" in mixed-sign cases, when it's actually negative. Strategy tip: In proof by cases with hypotheses, always check which cases are actually possible under the given conditions. Often, the hypothesis eliminates certain cases, making the proof more straightforward.

Question 12

In a proof by cases for "if $a$ and $b$ are integers with $a^2 + b^2$ even, then $a$ and $b$ have the same parity," what is the most significant logical flaw in considering only two cases: Case 1 (both $a$ and $b$ even) and Case 2 (both $a$ and $b$ odd)?

The case division omits mixed parity situations, but this omission is intentional since those cases would contradict the hypothesis.
The case division is incomplete because it fails to consider the cases where one variable is even and the other is odd.
The case division incorrectly assumes the conclusion, making the proof circular by only considering cases where the conclusion holds. (correct answer)
The case division is too narrow because it doesn't account for zero, which has special properties in parity arguments.

Explanation: This case division assumes what we're trying to prove. A proper proof by cases should consider all possible parity combinations: (even, even), (even, odd), (odd, even), and (odd, odd). Then show that only the first and last cases can satisfy the hypothesis a² + b² even, thus proving the conclusion. Choice A misunderstands the logical structure, Choice B identifies incompleteness but doesn't recognize the circularity, and Choice D incorrectly focuses on zero as a special case.

Question 13

To prove that " $\max(a,b) + \min(a,b) = a + b$ for all real numbers $a$ and $b$ ," a student uses proof by cases. The student considers Case 1: $a \leq b$ and Case 2: $a > b$ . In Case 1, what should the student's analysis conclude?

$\max(a,b) = a$ and $\min(a,b) = b$ , so $\max(a,b) + \min(a,b) = a + b$ , completing this case.
$\max(a,b) = b$ and $\min(a,b) = a$ , so $\max(a,b) + \min(a,b) = b + a = a + b$ , completing this case. (correct answer)
The case $a \leq b$ must be further subdivided into $a < b$ and $a = b$ to handle the boundary condition properly.
$\max(a,b) = \min(a,b) = \frac{a+b}{2}$ when $a \leq b$ , so the sum equals $a + b$ , completing this case.

Explanation: When a ≤ b, we have max(a,b) = b (the larger value) and min(a,b) = a (the smaller value). Therefore, max(a,b) + min(a,b) = b + a = a + b. Choice A incorrectly assigns max and min. Choice C unnecessarily subdivides the case since the inequality a ≤ b adequately covers both strict inequality and equality. Choice D incorrectly states that max and min both equal the average, which is never true unless a = b.

Question 14

A student attempts to prove "for any integer $n$ , at least one of $n$ , $n+2$ , $n+4$ is divisible by 3" using proof by cases. The student divides based on $n \pmod{3}$ and correctly handles the case $n \equiv 0 \pmod{3}$ . In analyzing the case $n \equiv 1 \pmod{3}$ , which number in the triple is divisible by 3?

$n$ itself, because $n \equiv 1 \pmod{3}$ and $1 \equiv 1 \pmod{3}$ means $n$ has remainder 1 when divided by 3.
$n + 2$ , because $n \equiv 1 \pmod{3}$ implies $n + 2 \equiv 3 \equiv 0 \pmod{3}$ , making it divisible by 3. (correct answer)
$n + 4$ , because $n \equiv 1 \pmod{3}$ implies $n + 4 \equiv 5 \equiv 2 \pmod{3}$ , which reduces to divisibility.
None of them individually, but their sum $3n + 6$ is always divisible by 3 regardless of the value of $n$ .

Explanation: If n ≡ 1 (mod 3), then n + 2 ≡ 1 + 2 ≡ 3 ≡ 0 (mod 3), so n + 2 is divisible by 3. Choice A is wrong because n has remainder 1, not 0. Choice C is incorrect since n + 4 ≡ 1 + 4 ≡ 5 ≡ 2 (mod 3), giving remainder 2. Choice D misses the point by discussing the sum rather than identifying which individual number in the triple is divisible by 3.

Question 15

To prove that "For all integers $a$ and $b$ , if $a^2 + b^2$ is divisible by 4, then both $a$ and $b$ are even," a student considers cases based on the remainders when $a$ and $b$ are divided by 2. How many cases must be analyzed, and which cases lead to a contradiction?

4 cases total; cases where exactly one of $a, b$ is even lead to contradictions, plus the case where both are odd leads to a contradiction (correct answer)
3 cases total; cases where $a$ is odd or $b$ is odd lead to contradictions, but these overlap so we only need to consider distinct remainder combinations
4 cases total; only the case where both $a$ and $b$ are odd leads to a contradiction, since $a^2 + b^2 \equiv 2 \pmod{4}$ in that case
2 cases total; case where at least one is odd leads to $a^2 + b^2 \not\equiv 0 \pmod{4}$ , and case where both are even satisfies the conclusion directly

Explanation: We need 4 cases: (1) both even, (2)

a

even,

b

odd, (3)

a

odd,

b

even, (4) both odd. When exactly one is odd,

a^2 + b^2 \equiv 1 \pmod{4}

, contradicting divisibility by 4. When both are odd,

a^2 + b^2 \equiv 2 \pmod{4}

, also contradicting divisibility by 4. Choice B incorrectly counts cases. Choice C misses that the mixed cases also lead to contradictions. Choice D oversimplifies by combining cases prematurely.

Question 16

Consider proving: "For any real number $x$ , $|x - 1| + |x - 3| \geq 2$ " using proof by cases based on the location of $x$ relative to the critical points. Which case division is both necessary and sufficient for a complete proof?

Case 1: $x \leq 1$ , Case 2: $x > 1$ , since this divides the domain based on the first critical point where the expression changes behavior
Case 1: $x \leq 0$ , Case 2: $0 < x < 1$ , Case 3: $1 \leq x \leq 3$ , Case 4: $x > 3$ , ensuring all possible positions relative to both critical points are covered
Case 1: $x < 3$ , Case 2: $x \geq 3$ , since the absolute value $|x - 3|$ has the larger coefficient effect on the sum
Case 1: $x < 1$ , Case 2: $1 \leq x < 3$ , Case 3: $x \geq 3$ , analyzing the behavior of each absolute value expression separately in each interval (correct answer)

Explanation: When proving inequalities involving absolute values, you need to identify the critical points where the expressions inside the absolute value bars equal zero, then analyze each resulting interval separately. For

|x - 1| + |x - 3| \geq 2

, the critical points are

x = 1

and

x = 3

, since these are where the absolute value expressions change their behavior. The correct approach divides the real line into three intervals based on both critical points:

x < 1

1 \leq x < 3

, and

x \geq 3

. In each interval, you can remove the absolute value bars by determining the sign of each expression. For

x < 1

: both

(x-1)

and

(x-3)

are negative, so

|x-1| = -(x-1)

and

|x-3| = -(x-3)

. For

1 \leq x < 3

(x-1) \geq 0

and

(x-3) < 0

. For

x \geq 3

: both expressions are non-negative. This three-case division in option D captures all necessary behavioral changes. Option A fails because it only considers one critical point, missing the behavioral change at

x = 3

. Option B unnecessarily includes

x = 0

, which isn't a critical point for either absolute value expression, creating redundant work. Option C also ignores the critical point at

x = 1

, focusing incorrectly on only the second absolute value term. Remember: for absolute value proofs, always identify ALL critical points where expressions inside the bars equal zero, then create cases for each interval between consecutive critical points.

Question 17

A student proves "If $x$ and $y$ are real numbers with $x^2 + y^2 = 1$ , then $-1 \leq x + y \leq \sqrt{2}$ " by considering cases based on the signs of $x$ and $y$ . Which case requires the most careful analysis to establish the upper bound $x + y \leq \sqrt{2}$ ?

Case where $x \geq 0$ and $y \geq 0$ , since both variables contribute positively to the sum and we need to find the maximum value subject to $x^2 + y^2 = 1$ (correct answer)
Case where $x \geq 0$ and $y \leq 0$ , since we need to balance the positive contribution of $x$ against the negative contribution of $y$ while maintaining the constraint
Case where $x \leq 0$ and $y \geq 0$ , since the analysis is symmetric to the previous case but requires separate verification of the bound
Case where $x \leq 0$ and $y \leq 0$ , since both variables contribute negatively and we need to ensure the sum doesn't fall below the lower bound of $-\sqrt{2}$

Explanation: The upper bound

x + y \leq \sqrt{2}

is achieved when both

x

and

y

are non-negative and as large as possible. Using Lagrange multipliers or the Cauchy-Schwarz inequality:

(x + y)^2 \leq 2(x^2 + y^2) = 2

, so

x + y \leq \sqrt{2}

with equality when

x = y = \frac{1}{\sqrt{2}}

. The case where both are non-negative requires the most careful analysis because it's where the maximum is achieved. Choices B and C involve mixed signs that naturally limit the sum. Choice D addresses the lower bound, not the upper bound.

Question 18

A student attempts to prove "If $n$ is an integer and $n^3 - n$ is odd, then $n$ is even" using proof by cases on the remainder when $n$ is divided by 3. What is the fundamental flaw in this approach?

The case division doesn't align with the logical structure of the problem, since $n^3 - n = n(n-1)(n+1)$ depends on consecutive integers, not residues modulo 3
The case division is correct but incomplete, since we need to consider residues modulo 6 to capture both the parity and divisibility by 3 simultaneously
The case division doesn't address the relevant parity properties, since $n^3 - n$ being odd depends on $n$ modulo 2, not modulo 3
The case division creates unnecessary work, since the statement can be proven directly by noting that $n^3 - n$ is always even for any integer $n$ (correct answer)

Explanation: The fundamental flaw is that

n^3 - n = n(n^2 - 1) = n(n-1)(n+1)

is the product of three consecutive integers, so one of them must be even, making the entire product even. Therefore,

n^3 - n

is never odd for any integer

n

, making the hypothesis of the conditional always false. The student's case division by residues modulo 3 is irrelevant because the statement is vacuously true. Choice A misidentifies the issue. Choice B suggests an unnecessary complication. Choice C focuses on the wrong modulus but misses that the hypothesis is impossible.

Question 19

To prove that " $\lfloor 2x \rfloor = 2\lfloor x \rfloor$ or $\lfloor 2x \rfloor = 2\lfloor x \rfloor + 1$ for any real number $x$ " using proof by cases, the critical case division depends on the fractional part of $x$ . What is the key threshold that determines which equality holds?

The threshold is whether the fractional part of $x$ is less than $\frac{1}{3}$ or at least $\frac{1}{3}$ , since this determines when doubling crosses an integer boundary
The threshold is whether the fractional part of $x$ is less than $\frac{1}{2}$ or at least $\frac{1}{2}$ , since this determines whether $2x$ has fractional part less than 1 (correct answer)
The threshold is whether $x$ itself is an integer or not, since integer values of $x$ always satisfy $\lfloor 2x \rfloor = 2\lfloor x \rfloor$
The threshold is whether the fractional part of $x$ is less than $\frac{2}{3}$ or at least $\frac{2}{3}$ , since this determines when the floor of $2x$ increases by an extra unit

Explanation: Let

x = n + f

where

n

is an integer and

0 \leq f < 1

is the fractional part. Then

2x = 2n + 2f

. If

f < \frac{1}{2}

, then

2f < 1

, so

\lfloor 2x \rfloor = \lfloor 2n + 2f \rfloor = 2n = 2\lfloor x \rfloor

. If

f \geq \frac{1}{2}

, then

2f \geq 1

, so

\lfloor 2x \rfloor = \lfloor 2n + 2f \rfloor = 2n + 1 = 2\lfloor x \rfloor + 1

. The threshold

\frac{1}{2}

is critical because it determines when

2f

crosses the integer boundary. Choices A and D use incorrect thresholds. Choice C is insufficient since it only addresses one case.

Question 20

Consider the statement: "For any integer $n \geq 2$ , either $n$ is prime or $n$ has a prime divisor $p$ with $p \leq \sqrt{n}$ ." A proof by cases divides based on whether $n$ is prime or composite. What additional insight is required to complete the composite case?

If $n$ is composite, then $n = ab$ where $1 < a, b < n$ . If both $a > \sqrt{n}$ and $b > \sqrt{n}$ , then $ab > n$ , a contradiction. So at least one factor is $\leq \sqrt{n}$ .
If $n$ is composite, then $n = ab$ where $1 < a, b < n$ . The smallest prime divisor of $n$ must divide either $a$ or $b$ , and by minimality must be $\leq \sqrt{n}$ .
If $n$ is composite, then $n = ab$ where $1 < a, b < n$ . We can assume $a \leq b$ , so $a^2 \leq ab = n$ , giving $a \leq \sqrt{n}$ . The smallest prime divisor of $a$ is $\leq a \leq \sqrt{n}$ . (correct answer)
If $n$ is composite, then by the fundamental theorem of arithmetic, $n$ has a unique prime factorization. The smallest prime in this factorization must be $\leq \sqrt{n}$ by the pigeonhole principle.

Explanation: Choice C provides the correct reasoning: if

n = ab

with

1 < a, b < n

, we can assume

a \leq b

without loss of generality. Then

a^2 \leq ab = n

, so

a \leq \sqrt{n}

. Since

a > 1

is composite or prime, it has a smallest prime divisor

p \leq a \leq \sqrt{n}

, and this

p

also divides

n

. Choice A shows one factor is

\leq \sqrt{n}

but doesn't ensure it's prime. Choice B incorrectly assumes the smallest prime divisor's location. Choice D misapplies the pigeonhole principle.