EECS 203: Discrete Mathematics

Fall 2024

Homework 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 = a/b. 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.

1. Collaboration and Support [3 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.

Mechanical Problems

2. Quantifier Quandary [14 points]

For each of the following propositions, state whether it is true or false when the domain of each quantifier is (i) the integers, and (ii) the real numbers. Justify each of your answers by either naming specific variable settings or by writing one sentence that suggests a general argument, as appropriate.

(a) ∃x(x3 = −1)

(b) ∃x(x2 = −1)

(c) ∃x(x4 < x2 )

(d) ∀x(2x > x)

(e) ∀x∃y(x2 − y = 0)

(f) ∀x∃y(y2 − x = 0)

(g) ∀x∃y(y2 = x or y2 = −x)

3. Pairwise Properties [9 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. Sum Stability [12 points]

(a) Prove or disprove: for all rational numbers x and y, x + y is rational.

(b) Prove or disprove: for all irrational numbers x and y, x + y is irrational.

In either part, you may use without justification that any integer is rational and that the number √2 is irrational, but you should include justification if you claim any other numbers to be rational or irrational.

5. Number Theory Negations [6 points]

Write the negation of each of the following propositions. Simplify as far as possible by pushing “not” (or similar words) inside logical expressions.

(a) There exists an integer a where a is not negative and a is not positive.

(b) For all integers b, b is rational or irrational.

(c) For all integers c, if c is even, then c + 1 is odd.

(d) For all integers d, d is positive if and only if d is not negative.

(e) There exists an integer e1 such that for all integers e2, e1 · e2 = e1.

(f) For all integers f1, there does not exist an integer f2 such that f2 > f1 and f2 ≤ f1.

6. For-All Flip [8 points]

Let P(x, y) be an unknown predicate.

(a) If ∀x∃yP(x, y), must it also be true that ∃y∀xP(x, y)?

(b) If ∃y∀xP(x, y), must it also be true that ∀x∃yP(x, y)?

For each part, either explain in a sentence or two why the proposition must also be true, or give a counterexample of a predicate P where it is false.

Bad Proofs

Each of the following propositions may or may not be true. We have given a “proof” that is correctly formatted, but which contains a logical error. Identify the error by citing a sentence, equation, or step, 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

4k2 + 4k + 1 − 1 = 4j

4k2 + 4k = 4j

k2 + k = j.

So since k is an integer, k2 + 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

since a square is always 0 or larger.

Since x, y are both integers, xy is an integer. All integers larger than −1/4 are at least 0, so xy ≥ 0.

9. Set Slip [6 points]

Proposition 3. Let a, b be integers and let S be a finitely-large set of integers such that

∃s1 ∈ S a|s1   and   ∃s2 ∈ S b|s2.

Then ab divides the product of all the integers in S.

Incorrect Proof. We can list the elements of S as S = {s1, s2, . . . , sc} , where we choose to write s1 (divided by a) first and s2 (divided by b) second. So we have s1 = ak1 and s2 = bk2 for some integers k1 and k2. The product of all the integers in S is

s1s2s3 . . . sc = (ak1)(bk2)s3 . . . sc

                         = (ab) · (k1k2s3 . . . sc).

Since k1, k2, s3, . . . , sc are all integers, we have that k1k2s3 . . . sc is an integer, which shows that ab divides the product of the integers in S.

Discovery Problems

10. Threepeat/Thirteen [15 points]

A threepeat is a positive integer that has exactly six digits, and where the first three digits are the same as the last three digits. For example, 203203 is a threepeat.

Which threepeats are divisible by 13? Is it all of them? None of them? Only the even ones? Only those that are large enough? Something else? Choose one of the following three propositions, and then give a proof of the proposition you choose:

• All threepeats are divisible by 13.

• No threepeats are divisible by 13.

• Some threepeats are divisible by 13, and others are not. A threepeat t is divisible by 13 if and only if

(if you choose this option, fill in the blank to complete a proposition).

11. 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? Choose one of the following three propositions, and then give a proof of the proposition you choose:

• All positive integers are happy.

• No positive integers are happy.

• Some positive integers are happy, and others are not. A positive integer h is happy if and only if

(if you choose this option, fill in the blank to complete a proposition).

Groupwork

1. Diag Squirrels [15 points]

Sammy and Sapphire the Diag Squirrels are playing a game. Sammy and Sapphire take turns, starting with Sammy. There is a row of 5 holes, each starting with 203 acorns in it. On each turn, a squirrel picks a hole, eats exactly one acorn from it, then places up to 3 new acorns in each hole to the right of that hole. If none of the holes have any acorns left, meaning the squirrel can’t eat any acorns on their turn, they lose.

The goal of this question is to prove that Sammy can play the game in a way that guarantees they will win.

(a) Prove that if all holes have an even number of acorns, then all legal moves leave at least one hole with an odd number of acorns.

(b) Prove that if at least one hole has an odd number of acorns, then there exists a legal move that leaves all holes with an even number of acorns.

(c) Prove that there exists a strategy that Sammy can use to play the game to guarantee they will win. (Note that the leftmost hole can only be picked 203 times, and the next hole can only be picked 203 + 203 · 3 times, and so on, so the game always ends. You may assume this without further proof.)

2. Lying and Politics [15 points]

There are two kinds of people in the world: knights and knaves, where knights always tell the truth and knaves always lie. There are three people, Alice, Bob, and Charlie, and one of them is the city mayor.

• Alice says “I am not the city mayor.”

• Bob says “The city mayor is a knave.”

• Charlie says “All three of us are knaves.”

Is the city mayor a knight or a knave? Explain your answer.