Massachusetts Institute of Technology Handout 26 6.042J/18.062J: Mathematics for Computer Science March 15 2000 Professors David Karger and Nancy Lynch

Quiz 1 Solutions

Problem 1 [10 points] Quantifiers Consider the following predicates where the universe of discourse is the set of all people: P (x): x is a hacker Q(x): x is an MIT student R(x): x is an artist S(x): x is willing to waltz Express each of the following statements using quantifiers, logical connectives, and and the above predicates:

(a) [1 point] No hackers are willing to waltz. Solution. ∄x P (x) ∧ S(x)

(b) [1 point] No artists are unwilling to waltz. Solution. ∄x R(x) ∧ ¬S(x)

(c) [1 point] All MIT students are hackers. Solution. ∀x Q(x) ⇒ P (x)

(d) [1 point] MIT students are not artists. Solution. ∀x Q(x) ⇒ ¬R(x)

(e) [4 points] Does (d) follow logically from (a), (b), and (c)? If so, give a proof. If not, give a counterexample. Solution. Assume (a), (b), and (c). Then, we want to prove that, for any x such that Q(x) (for any MIT student), it follows that ¬R(x) (that student is not an artist). From (c), we know that P (x) (that the student is a hacker). If we rearrange (a) to

∀x P (x) ⇒ ¬S(x)

then clearly ¬S(x) (the student is not willing to waltz). So, if we rearrange (b) to

∀x ¬S(x) ⇒ ¬R(x)

it follows that ¬R(x) (the student is not an artist).

Handout 26: Quiz 1 Solutions  2  Name:

(f) [1 point] Translate into English: (∀x)(R(x) ∨ S(x) ⟹ Q(x)). Solution. All who are artists or people willing to waltz are MIT students.

(g) [1 point] Translate into English: (∃x)(R(x) ∧ ¬Q(x)) ⟹ (∀x)(P (x) ⟹ S(x)). Solution. If there is an artist who is not an MIT student, then all hackers are willing to waltz.

Problem 2 [10 points] Induction Prove by induction (other methods will not receive credit) that

(1 · 2) + (2 · 3) + (3 · 4) + ⋯ + (n − 1)n = \frac{1}{3}(n − 1) · n · (n + 1)

whenever n is a natural number greater than 1. Solution. Prove P (n) ::= (1 · 2) + (2 · 3) + (3 · 4) + ⋯ + (n − 1)n = \frac{1}{3}(n − 1) · n · (n + 1) Basis. (P (2)) (1 · 2) = \frac{1}{3}(1) · 2 · (3). Induction. Assume P (n). Prove P (n + 1).

\underbrace{(1 · 2) + (2 · 3) + (3 · 4) + ⋯ + (n − 1)n}_{Apply IH} +n(n + 1) = \frac{1}{3}(n − 1) · n · (n + 1) + n(n + 1)
= n(n + 1) [\frac{1}{3}(n − 1) + 1]
= n(n + 1) [\frac{1}{3}n + \frac{2}{3}]
= \frac{1}{3}n(n + 1) [n + 2]

Problem 3 [10 points] Structural Induction Consider the sets S_{1}, S_{2}, … defined inductively as

• S_{0} = {0, 1}

• For all n ≥ 1, S_{n} = \{\frac{x+y}{2} | x, y ∈ S_{n−1}\} i.e., where S_{n} contains the average values of each pair of numbers in S_{n−1}. Note we allow x = y in the definition of S_{n}.

(a) [1 point] Write out the elements of each of the following sets: S_{1}, S_{2}, and S_{3}. Solution.

\begin{matrix}S_{1} & \{0, 1/2, 1\} \\ S_{2} & \{0, 1/4, 1/2, 3/4, 1\} \\ S_{3} & \{0, 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, 1\} \end{matrix}

Handout 26: Quiz 1 Solutions  3  Name:

(b) [2 points] Generalize (in your own words or in symbols) to give the elements of S_{n}. Solution. S_{n} contains 2^{n} + 1 elements (including 0 and 1) evenly spaced along the unit interval; i.e., S_{n} = {i/2^{n}|0 ≤ i ≤ 2^{n}}.

(c) [7 points] Prove by induction that for all n ∈ ℕ, 1/3 ∉ S_{n}. You will probably want to strengthen the induction hypothesis. You may not assume your generalization from the previous part is true; you must prove that statement if you wish to use it. Solution. Strengthen the theorem to

P (n) = “For all a/b ∈ S_{n} with a, b ∈ ℕ where a/b is in reduced form, b = 2^{k} for some k”

Clearly, if ∀n P (n), then ∀n 1/3 ∉ S_{n}. Thus, we need only prove ∀n P (n). Base cases. 0 = 0/2^{0}, 1 = 1/2^{0}. Induction. Assume P (n). By the construction of S_{n+1}, all elements of S_{n+1} are of the form (x + y)/2 for some x, y ∈ S_{n}. Fix any two such elements x, y ∈ S_{n}, where (by the induction hypothesis) x = a/2^{k} and y = c/2^{ℓ} with a, b, k, ℓ ∈ ℕ. Assume WLOG k ≥ ℓ. Then,

(x + y)/2 = (a/2^{k} + c/2^{ℓ})/2
= (a/2^{k} + c2^{k−ℓ}/2^{k})/2
= (a + c2^{k−ℓ})/2^{k+1}

While this may not be in reduced form, reduction cannot introduce any non-2 factors into the denominator, so this fits the form specified by the theorem. Therefore, P (n + 1). By induction, ∀n P (n). Thus, ∀n 1/3 ∉ S_{n}.

Problem 4 [10 points] Relations

(a) [1 point] What is the common name for the reflexive closure of the “less than” relation? Solution. less than or equal to

(b) [1 point] What is the common name for the transitive closure of the “child of” relation? Solution. descendant of

Handout 26: Quiz 1 Solutions  4  Name:

(c) [2 points] What is the common name for the inverse of the “teaches” relation (that is, if xT y means x teaches y, how do we say aT^{−1}b)? Solution. is taught by (d) [3 points] Consider the partial order “aRb iff a divides b without remainder” on the universe of natural numbers greater than 1. What are the minimal elements under this relation usually called?

Solution. primes

(e) [3 points] Is the relation “xRy iff x = y or x is not y’s roommate” an equivalence relation? Why or why not?

Solution. No, because it is not transitive. If x and y are roommates but neither is a roommate of z, then xRz and zRy but ¬xRy.

Problem 5 [10 points] Precedence Relations

Death is planning the end of the world. This involves a number of tasks each of which takes one minute to complete. The prerequisites associated with these tasks are listed below.

Abbrv. Task  Prerequisites
C  Compose a requiem
N  Notify the UN  B
D  Signal the daemons  B
B  Blow the trumpet
T  Sell T-shirts: “All I got was this lousy t-shirt.” N
Q  Grade the 6.042 quiz  S
G  Open the gates  D,N
S  Put out the sun  C,N

(a) [5 points] Represent the tasks and their prerequisites as a directed graph.

Solution. This is very similar to the constructions in the notes.

(b) [5 points] Death is omnipotent and can therefore work on as many tasks at a time as he wishes. What is the minimum amount of time required for him to end the world? Why? (An explanation without proof is fine.)

Solution. 4 time units, since that is the length of the critical path.

Problem 6 [5 points] Graphs

Let G = (V, E) be a simple, undirected graph, and let C be a set of colors. Define a partial coloring of G using C to be a function that assigns to each node in V either a color in C or no color. (That is, it colors some, none, or all of the nodes using colors in C.) Define a partly colored graph to be a simple, undirected graph G = (V, E) together with a partial coloring of G.

Prove the following fact about partly colored graphs:

In a partly colored graph, any walk connecting a colored node to an uncolored node must include a colored node adjacent to an uncolored node.

Solution. Consider the path p = v_{1}v_{2} ⋯ v_{k}, of which v_{1} is colored and v_{k} is uncolored. Assume there is no edge (v_{i}, v_{i+1}) such that v_{i} is colored and v_{i+1} is uncolored. Then, by induction starting from v_{1}, v_{i} are colored for all i, so v_{k} is colored; this is a contradiction.

Problem 7 [15 points] Algorithms

Let G = (V, E) be a simple, undirected graph. The following algorithm, RedBlue, manipulates partial colorings of G using C = {red, blue}. (Partial colorings are defined in the previous problem.)

Initially, one vertex r of G is colored red, and all the other vertices are uncolored. At each step, one of two events occurs:

a) Some uncolored vertex v that is adjacent to a red vertex becomes blue.

b) Some uncolored vertex v that is adjacent to a blue vertex becomes red.

If neither rule can be applied, the algorithm terminates.

(a) [3 points] Formalize this algorithm as a state machine; that is, define Q, Q_{0}, and δ.

Solution. A state q consists of a (total) function f from V to {red, blue, uncolored}. A start state is any state in which f maps exactly one v ∈ V to red, and all others to uncolored. The transitions are all of the form:

(q, q′) ∈ δ ⟺ ∃v ∈ V q.f(v) = uncolored
∧[ (q′.f(v) = red ∧ ∃w f(w) = blue ∧ (v, w) ∈ E)
∨ (q′.f(v) = blue ∧ ∃w q.f(w) = red ∧ (v, w) ∈ E) ]
∧∀w ≠ v q.f(w) = q′.f(w)

(b) [3 points] Prove that the algorithm eventually terminates.

Solution. We describe a termination function. Define the value of the termination function to be the number d of uncolored vertices. Each step decreases d, so we can appeal to the Termination Theorem and conclude that the algorithm always terminates. Alternatively, we can expand the proof a bit more: since d starts at n−1 and is always ≥ 0, it must eventually reach some minimum value (by well-ordering), whereupon the algorithm terminates.

(c) [3 points] Using the fact stated in Problem 6, prove that if G is connected, then all vertices are colored when the algorithm terminates.

Solution. Say the algorithm terminates with some vertex uncolored. Since the graph is connected, there is a path from v to some colored vertex w. By the given fact, there must be an edge along this path for which one endpoint x is colored and the other y is uncolored. We can apply one of the two steps above, assigning to y the opposite of x’s color. Thus, the algorithm should not have terminated yet.

(d) [3 points] Consider applying this algorithm to bipartite graphs, i.e., graphs in which the vertices can be partitioned into two sets A and B such that there is no edge between any pair of vertices in A, and similarly for B. Suppose the node r that is colored red in the initial state is in set A. Using the Invariant Theorem, prove that in any reachable state, only vertices of A are colored red and only vertices of B are colored blue.

Solution. The Invariant Theorem requires that we show some condition is true in all the start states, and that it is preserved by every step.

P (n) =“After n vertices are colored, all red vertices are in A and all blue vertices are in B.”

Base case. In any start state, there is exactly one red vertex in R—by construction—and no blue vertices. Therefore, P (1).

Induction. Assume P (n). Then, consider an execution in which n + 1 vertices are colored. Consider the vertex i which was colored last. If we uncolor it, we can apply the induction hypothesis and conclude that all red vertices were in R and all blue vertices were in B.

Now we must prove that vertex i is colored correctly. Assume WLOG that vertex i is in B. For i to have been colored, it must have been the case that i was adjacent to a colored vertex; but all vertices adjacent to i are in R (by the definition of bipartite), so i must have been colored blue. This satisfies the invariant theorem, so P (n + 1).

Thus, ∀n P (n), so all red vertices are in R and all blue vertices are in B.

(e) [3 points] Combine the previous parts to prove that when run on a connected bipartite graph, the above algorithm terminates and outputs a valid 2-coloring.

Solution. We proved the algorithm terminates on connected graphs with all vertices colored. By the invariant above, this means all vertices in R are red and all vertices in B are blue. By the definition of bipartite, there exists no pair of like-colored vertices connected by an edge, so this is a valid 2-coloring.