EECS 203: Discrete Mathematics

Winter 2026 Homework 2

Due Thursday, Jan. 29, 10:00 p.m.

No late homework accepted past midnight.

Number of Problems: 10 Total Points: 100

• Match your pages! Your submission time is the time you upload the file, so the time
you take to match pages does not count against you.

• Submit this assignment (and any regrade requests later) on Gradescope.

• Justify your answers and show your work (unless a question says otherwise).

• By submitting this homework, you agree that you are in compliance with the Engi-
neering Honor Code and the Course Policies for 203, and that you are submitting your
own work.

• Check the syllabus for full details.

1
Reminders
• The integers are the set {. . . , −2, −1, 0, 1, 2, . . . }. The real numbers are
√ the set of all
(non-imaginary, non-infinity) numbers, including all the integers, e, π, 2, −0.203, etc.

• The notation ∃ means “there exists” and ∀ means “for all.”

• An integer x is even if there exists an integer k with x = 2k. An integer x is odd if

there exists an integer k with x = 2k + 1.

• An integer k divides an integer x, written k | x, if there exists an integer j with x = jk.

• The greatest common divisor of two or more integers is the largest integer that divides
all of those integers.

• A real number x is rational if there exist integers a and b with x = ab . Otherwise, x is

irrational.

• You may assume any of the following without proof: the laws of algebra are valid, the
sum or difference of two integers is an integer, the product of two integers is an integer.

• List of some Equivalence Laws:

– Domination Law: T ∨ x ≡ T , and F ∧ x ≡ F
– Identity Law: T ∧ x ≡ x, and F ∨ x ≡ x
– Idempotent Law: x ∨ x ≡ x, and x ∧ x ≡ x
– Double Negation Law: ¬¬x ≡ x
– Negation Law: x ∧ ¬x ≡ F , and x ∨ ¬x ≡ T
– Commutative Law: a ∨ b ≡ b ∨ a, and a ∧ b ≡ b ∧ a
– Associative Law: (a ∨ b) ∨ c ≡ a ∨ (b ∨ c), and (a ∧ b) ∧ c ≡ a ∧ (b ∧ c)
– Distributive Law: a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c), and a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c)
– DeMorgan’s Law: ¬(p ∧ q) ≡ ¬p ∨ ¬q, and ¬(p ∨ q) ≡ ¬p ∧ ¬q
– Implication Breakout: p → q ≡ ¬p ∨ q

2
1. Reflection [14 points]
Carefully read and understand the posted solutions to the previous homework. Identify one
part of a question (for example, part (a) of Question 3) where you think your own solution
has the most room for improvement. This could be the solution for which you lost the most
points (self-grade, since official grades are not out yet), felt you had unsound reasoning,
needed better organization, or any other metric of your choice.
Copy or screenshot your solution. Then in a few sentences, explain why you chose this
question and how your solution could be improved.
Notes:
• You must complete this question even if you anticipate getting full credit on the previ-
ous homework: just because you may get all the points doesn’t necessarily mean that
there isn’t something that could have been improved! If this applies to you, we encour-
age you to be creative about what metric or axis you use to measure improvement.

• If you did not do last week’s homework, choose a problem from it that looks challenging
to you, and in a few sentences, explain the key ideas behind its solution in your own
words.

Mechanical Problems

2. Serious Implications [6 points]

Show that (b → a) ∧ (c → a) is logically equivalent to ¬(b ∨ c) ∨ a using
(a) a truth table.

(b) a logical equivalence proof. Be sure to cite every law you use.
Note: Make sure to show your work. For a truth table, that means including columns for
intermediate expressions as well as the final expression(s) and explaining how/why the truth
table shows that the two expressions are equivalent.

3. I’m Prime, Two! [5 points]

Prove that for all prime numbers p, if p ̸= 2, then p is odd.
Note: You may NOT use the argument that all prime numbers greater than 2 are odd. This
is what you are proving.

3
4. Contra > 0 [9 points]
Prove or disprove: if n3 + 2 is divisible by 3, then n is not divisible by 3.

5. Irrational Pr00f [9 points]

Prove or disprove that the product of a nonzero rational number and an irrational number
is irrational.

6. Pay it Forward (or Don’t, It’s Up to You) [6 points]

Consider a game with two players, P1 and P2, which begins with P1’s turn and $1 in prize
money. On each turn, the current player chooses one of the following actions:
• Take: The player takes all of the prize money and the game ends.

• Wait: The player leaves the prize money, the prize money increases by $1, and the
turn passes to the other player.
However, the maximum amount of prize money is $20. Once the prize money has reached
$20 it will not increase any further even if a player chooses to Wait.
Suppose both P1 and P2 behave as perfect logicians, and both want to maximize their
winnings. Prove that P1 should take $1 in the very first round.
Hint: Consider what would happen when the prize money reaches $20, and work backwards
from there.

7. Root 2. . . k? [9 points]
√
Let x = 2k where k is a positive odd integer. Prove that x is irrational.
Note: You may use results proven previously in lecture or discussion

Bad Proofs
Each of the following propositions may or may not be true, but we have given an incorrect
“proof” that attempts to show that it is true. Identify the specific logical error made in each
proof by citing a sentence, equation, step, or missing part of the proof, and briefly explain
why it is wrong.

4
8. Contra-Positively Incorrect [6 points]
Proposition 1. For all integers a and b, if b4 + ba3 + b ≤ a4 + ab3 + a, then b ≤ a.

Incorrect Proof. We will prove the contrapositive: There exist integers a and b such that if
b > a then b4 + ba3 + b > a4 + ab3 + a.
Consider a = 1, b = 2.
b4 + ba3 + b = 24 + 2(13 ) + 2 = 20.
a4 + ab3 + a = 14 + 1(23 ) + 1 = 10.
Since 20 > 10, we have shown b4 + ba3 + b > a4 + ab3 + a. Thus, we have proven the
contrapositive statement and therefore the original proposition is proven.

9. Dastardly Divisors [6 points]

A student wants to prove or disprove the following proposition:

Proposition 2. For all integers n, if n is odd, then 4|(n2 − 1).

Incorrect Disproof. We will disprove by proving the negation: There exists an integer n such
that, if n is odd, then 4 ∤ (n2 − 1).
Consider n = 2. This makes “if” part of the negation false (since n is not odd), and the
“then” part true (since 4 ∤ 22 − 1, i.e., 4 ∤ 3) so the negation evaluates to F → T , which is
T . Thus we have proven the negation, i.e., we have disproven the original statement.

Discovery Problems

10. Consecutive Counting [15 points]

A positive integer h is happy if the sum of any h consecutive integers is divisible by h. For
example, 203 is happy if the number 1 + 2 + 3 + · · · + 203 is divisible by 203, and the number
2 + 3 + 4 + · · · + 204 is divisible by 203, and so on.
Which positive integers are happy? Is it all of them? None of them? Only the even ones?
Only those that are large enough? Something else?
(a) Complete the proposition below by filling in the blank:

A positive integer h is happy if and only if .

5
 (b) Prove the proposition stated in part (a).
Hint: In your proof, it may be helpful to write out the sum of h consecutive integers
generically, where the first term in the sum is an integer a.

11. Primes All the Way Down [15 points]

In this problem, we show that every natural number n > 1 can be written as the product of
prime numbers. Note: The natural numbers are defined to be the set N = {0, 1, 2, . . . }.
Note: A single prime number p is considered to be a product of prime numbers (where the
only prime number in the product is p).
(a) Fill in the blank to complete the beginning of the proof.

Suppose for the sake of contradiction that there exists a natural number greater than
1 with the property that it .
Let n0 be the smallest natural number with this property.

(b) Complete the proof begun in part (a).