EECS 203: Discrete Mathematics

Winter 2025
Homework 1

Due Thursday, Jan. 22, 10:00 pm

No late homework accepted past midnight.
Number of Problems: 11 Total Points: 100

• Match your pages! Your submission time is when you upload the file, so the time
you take to match pages doesn’t 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 (where b ̸= 0) 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.

Note on Future Homework Question 1’s

As a staff, we find that evaluating your previous work is enriching the learning process.
While it is not present on this homework, all subsequent homeworks will have a similar
question one asking you to evaluate an answer to a question on the previous homework.
More details will be provided in the question.

1. Collaboration and Support [14 points]

(a) Give the names and uniqnames of 3 of your EECS 203 classmates (these could be
members of your homework group or other classmates).

(b) When you have questions about the course content, where can you ask them? Where
are you most likely to ask questions?

(c) Name one self-care action you plan to do this semester to maintain your overall well-
being.

2
Mechanical Problems

2. On (quanti-)Fire [9 points]
Determine the truth value of each of these statements where the domain of each quantifier
is (i) the integers, and (ii) the real numbers. Justify your answer.
(a) ∃x(x4 < 0)

(b) ∃x(x4 = 2)

(c) ∀x(x2 + 2x + 1 ≥ 0)

(d) ∀x(x4 ≥ x3 )

(e) ∀x∃y(2y = x + 1)

(f) ∀y∃x(2y = x + 1)

(g) ∃x∀y(2y = x + 1)

3. Pairwise Properties [11 points]

(a) Prove or disprove: there exist three integers x, y, z where the minimum of all three is
1, but for each pair of integers (x, y), (x, z), and (y, z), the minimum of that pair is
not 1.

(b) Prove or disprove: there exist three integers x, y, z where the greatest common divisor
of all three is 1, but for each pair of integers (x, y), (x, z), and (y, z), the greatest
common divisor of that pair is not 1.

4. Rationale Behind Rational [10 points]

A number is rational if it can be written as a ratio of two integers. More formally, x is
rational if there exist integers a and b ̸= 0 so that x = ab .
(a) Prove that the product of two rational numbers and the sum of two rational numbers
is rational.

(b) Use your conclusion from part (a) to prove that if a, b, c, d, and e are rational then
(a + b)2 (c + d + e) is rational. Do not explicitly use the definition of rational in your
proof.

3
5. Even It Out [8 points]
Prove that for any integers n and m, if n2 + m2 is even, then n + m is even.
Note: You may use the following properties without proof:
(i) If n2 is odd, then n is odd.

(ii) If n2 is even, then n is even.

6. Who Framed Roger Rabbit [12 points]

Translate these statements into English, where R(x) is “x is a rabbit” and H(x) is “x hops”
and the domain consists of all animals. One of your answers must be “all rabbits hop,” and
another must be “at least one rabbit hops” to receive full credit.
(a) ∀x (R(x) → H(x))

(b) ∀x (R(x) ∧ H(x))

(c) ∃x (R(x) → H(x))

(d) ∃x (R(x) ∧ H(x))

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.

7. Oddness Oversight [6 points]

Proposition 1. For all odd integers n, we have 4 | (n2 − 1).

Incorrect Proof. Let n be any odd integer. Since n is odd, we have n = 2k + 1 for some
integer k. Since 4 | (n2 − 1), we have n2 − 1 = 4j for some integer j. So

(2k + 1)2 − 1 = 4j
4k 2 + 4k + 1 − 1 = 4j
4k 2 + 4k = 4j
k 2 + k = j.

4
So since k is an integer, k 2 + k is an integer, which agrees with the fact that j is an integer,
so the proof is complete.

8. Positivity Prank [6 points]

Proposition 2. For all even integers x and odd integers y, we have xy ≥ 0.

Incorrect Proof. Let x be any even integer and let y be any odd integer. Since x is even, we
have x = 2k for some integer k. Since y is odd, we have y = 2k + 1 for some integer k. So

xy = 2k(2k + 1)
= 4k 2 + 2k
 
2 1 1
= 4k + 2k + −
4 4
 2
1 1
= 2k + −
2 4
1
≥− since a square is always 0 or larger.
4
Since x, y are both integers, xy is an integer. All integers larger than −1/4 are at least 0, so
xy ≥ 0.

9. Even More Odd [6 points]

Proposition 3. For all integers x, y if x + y is even, then x is even and y is even.

Incorrect proof: Let x and y be any integers. Assume x is even and y is even. By definition,
x = 2k for some integer k and y = 2j for some integer j.
So x + y = 2k + 2j = 2(k + j) = 2m where m is some integer.
Therefore x + y must be even by definition, which proves that if x + y is even, then x is even
and y is even.

5
Discovery Problems

10. Distraught Dispensers [9 points]

Suppose there is a vending machine that sells CokeTM and SpriteTM . This particular vending
machine has 3 dispensers, one for CokeTM , one for SpriteTM , and one that dispenses either a
CokeTM or a SpriteTM at random. There’s just 1 problem, all of the labels for the dispensers
have been mixed up and are incorrect! How many times do you have to buy a drink in order
to know definitively which dispenser dispenses what?

Note: each dispenser has a unique, incorrect label matching one of SpriteTM , CokeTM ,
or Random.

11. Treasure Hunt [9 points]

Imagine a world with two kinds of people: knights and knaves, where knights always tell the
truth and knaves always lie.

You encounter 3 people, each guarding a door. You know that one door has treasure behind
it, while the other two lead to empty rooms.
• A says, “B and C are both knaves.”

• A says, “The treasure is behind my door.”

• B says, “The treasure is behind C’s door.”

• C says, “The treasure is behind A’s door.”

Which door has the treasure, and what are the roles of the three people?