Massachusetts Institute of Technology Midterm Solutions 6.042J/18.062J: Mathematics for Computer Science November 4, 1998 Professors Nancy Lynch and Srinivas Devadas

Midterm Solutions

Problem 1. (6 points) Consider the following proposition.

∀x∀y (x < y → ∃z (x < z ∧ z < y))

(a) (2 points) Prove or disprove this proposition, assuming that the universe is the set of integers.

The proposition is false. In the case where x = 0 and y = 1, there does not exist an integer z such that x < z and z < y.

(b) (4 points) Write the negation of this proposition. Your solution may not use the ¬ symbol, but may use any of the relations =, <, >, ≤, or ≥.

∃x∃y (x < y ∧ ∀z (x ≥ z ∨ z ≥ y))

Problem 2. (10 points) Define the matrix

M = [ \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ] .

Let M^{n} denote the product of n copies of the matrix M. Use ordinary induction to prove that for all n ≥ 1, the upper right entry of M^{n} is F_{n}, the n-th Fibonacci number. State your inductive hypothesis clearly.

For reference, the standard formula for the product of 2 × 2 matrices is given below.

[ \begin{matrix}a & b \\ c & d \end{matrix} ] · [ \begin{matrix}e & f \\ g & h \end{matrix} ] = [ \begin{matrix}ae + bg & af + bh \\ ce + dg & cf + dh \end{matrix} ]

Recall that F_{0} = 0, F_{1} = 1, F_{2} = 1, F_{3} = 2, ….

Proof. The proof is by induction. Let P (n) be the proposition that

M^{n} = [ \begin{matrix}F_{n−1} & F_{n} \\ F_{n} & F_{n+1} \end{matrix} ] .

In the base case, P (1) is true because

M^{1} = [ \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ]
= [ \begin{matrix}F_{0} & F_{1} \\ F_{1} & F_{2} \end{matrix} ] .

In the inductive step, for n ≥ 1 assume P (n) to prove P (n + 1). The following equalities hold.

M^{n+1} = M^{n} · M
= [ \begin{matrix}F_{n−1} & F_{n} \\ F_{n} & F_{n+1} \end{matrix} ] · [ \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ]
= [ \begin{matrix}F_{n} & F_{n−1} + F_{n} \\ F_{n+1} & F_{n} + F_{n+1} \end{matrix} ]
= [ \begin{matrix}F_{n} & F_{n+1} \\ F_{n+1} & F_{n+2} \end{matrix} ]

The first step uses the definition of M^{n}. The second step uses the induction hypothesis and the definition of the matrix M. We carry out a matrix multiplication in the third step and use the Fibonacci recurrence in the last step. This shows that P (n) implies P (n + 1), and the claim is proved by induction.

Problem 3. (12 points) The vertices of a directed graph can be partitioned into stronglyconnected components. Two vertices u and v belong to the same strongly connected component if there is a path from u to v and a path from v to u. A strongly connected component may consist of a single vertex.

Theory Pig has noticed a strange phenomenon. He starts with a directed graph and partitions the vertices into strongly-connected components. He then removes all edges that connect two vertices in the same strongly-connected component. The resulting graph always seems to be acyclic.

An example is worked out in the figure below. The original directed graph is shown on the left. The vertices a, b, and c form one strongly-connected component. The single vertex d forms a second strongly-connected component. Theory Pig removes the edges a → b, b → c, and c → a, since these edges connect vertices in the same strongly-connected component. The resulting graph is shown on the right. Note that this graph is acyclic.

Use proof by contradiction to show that for every directed graph, application of Theory Pig’s procedure gives a directed acyclic graph.

Proof. Let G = (V, E) be an arbitrary directed graph. Let G′ = (V, E′) be the directed graph that remains after we remove all edges that connect two vertices in the same stronglyconnected component.

The proof is by contradiction. Suppose that G′ is not acyclic. Then let u and v be consecutive nodes in a directed cycle. There is a path from u to v consisting of a single edge. There also is a path from v to u, because the nodes are in a cycle. Since every edge in G′ is also in G, these same two paths exist in the original graph G. Therefore, u and v are in the same strongly-connected component of G. But then the edge from u to v should have been removed during the construction of G′. Since the the edge was not removed, we have a contradiction. Therefore, G′ is acyclic.

Problem 4. (12 points) One of the three monks working on the famed Towers of Hanoi project recently rubbed his pained back and burst out, “Yo! What are we doing? This is for chumps! Let’s punt!” But before wandering off to start up fast food joints, they must evenly divide the monastery’s collection of prayer beads.

Initially, monk A has 5 beads, monk B has 3 beads, and monk C has 4 beads. The monastic order has strict rules regarding the exchange of prayer beads. Only the following transactions are allowed.

1. Monk B may give a bead to monk A at any time.

2. If C has an odd number of beads, then monk A may give a bead to monk B.

3. If C has an even number of beads or monk A has at least two more beads then monk B, then monk C may give or take a bead from either monk A or monk B.

(a) (3 points) Model the situation with a state machine. Define the set of states,the set of start states, and the set of transitions.

The set of states Q consists of all triples (a, b, c) such that a, b, c ≥ 0 and a+b+c = 12. The set of starts states Q_{0} consists of the single triple (5, 3, 4). The set δ contains six types of transition:

(a, b, c) → (a + 1, b − 1, c) (b > 0)
(a, b, c) → (a − 1, b + 1, c) (a > 0 and c is odd)
(a, b, c) → (a − 1, b, c + 1) (a > 0 and either c is even or a ≥ b + 2)
(a, b, c) → (a, b − 1, c + 1) (b > 0 and either c is even or a ≥ b + 2)
(a, b, c) → (a + 1, b, c − 1) (c > 0 and either c is even or a ≥ b + 2)
(a, b, c) → (a, b + 1, c − 1) (c > 0 and either c is even or a ≥ b + 2)

(b) (3 points) Prove that the monks can reach the state where monk A has 0 beads, monk B has 9 beads, and monk C has 3 beads by describing a sequence of steps leading to this state.

Initially, monk C gives a bead to monk B using rule 3. Then monk A gives his 5 beads to monk B using rule 2 repeatedly.

(c) (6 points) Prove that the monks can not reach the state where every monk has 4 beads by using the Invariant Theorem.

Proof. The proof uses the Invariant Theorem. We prove that if monk C has an even number of beads, then monk A has more beads than monk B. This implies that the monks can never evenly divide up the prayer beads; an even division would require that C have 4 beads, but then the invariant would imply that A has more beads then B.

The invariant holds in the single start state Q_{0}, since in this case monk C has an even number of beads (4), and monk A has more beads than monk B (5 vs. 3). Furthermore, if the invariant holds before a transition, then it holds after a transition. There are six cases to check, corresponding to the six types of transition.

1. (a, b, c) → (a + 1, b − 1, c) where b > 0. If c is odd, then the invariant holds after the transition because the hypothesis of the invariant if false. If c is even, then the invariant holds after the transition because a + 1 > a > b > b − 1.

2. (a, b, c) → (a − 1, b + 1, c) where a > 0 and c is odd. The invariant holds after the transition because the hypothesis of the invariant is false.

3. (a, b, c) → (a − 1, b, c + 1) where a > 0 and either c is even or a ≥ b + 2. If c is even, then the invariant holds after the transition because the hypothesis is false. If c is odd, then the invariant holds after the transition because the conclusion is true; that is, monk A has more beads than monk B.

The argument in the remaining three cases is identical to the argument for case 3. Since the invariant hold in all start states and is maintained under all transitions, the claim is proved by the Invariant Theorem.

Problem 5. (5 points) Find a closed-form expression equal to the following summation.

∑_{j=1}^{n} ∑_{i=0}^{∞} \sqrt{j} · (1 − \frac{1}{2\sqrt{j}} )^{i}

∑_{j=1}^{n} ∑_{i=0}^{∞} \sqrt{j} · (1 − \frac{1}{2\sqrt{j}} )^{i} = ∑_{j=1}^{n} \frac{\sqrt{j}}{1 − (1 − \frac{1}{2\sqrt{j}} )}

= 2 · ∑_{j=1}^{n} j

= 2 · \frac{n(n + 1)}{2}
= n(n + 1)

First, we use the formula for the sum of an infinite geometric series to eliminate the inner summation. After simplifying, we apply the formula for the sum of an arithmetic series.

Problem 6. (8 points) Order the functions listed below so that each function is either O or Θ of the next function. Indicate whether the stronger Θ relationship holds in each case. No proofs are required.

• F_{n}, the n-th Fibonacci number

• G(n), the number directed graphs with vertices {1, 2, 3, …, n} (self-loops permitted)

• P (n), the number of permutations of an n-element set

• M(n), the number of n × n matrices with only 0’s and 1’s as elements

We rewrite these quantities in simpler forms to make comparison possible. First, F_{n}, the n-th Fibonacci number is equal to:

F_{n} = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n} − \frac{1}{\sqrt{5}} (\frac{1 − \sqrt{5}}{2})^{n}

= Θ ((\frac{1 + \sqrt{5}}{2})^{n})

The Θ relation holds because the second term on the right approaches zero. The quantity (1 + \sqrt{5})/2 is 1.618 …, but any approximation between 1 and 2 will suffice for this problem.

Next, consider G(n). The possible edge sets of a directed graph with vertices {1, 2, 3, …, n} are the subsets of {1, 2, 3, …, n} × {1, 2, 3, …, n}. By the product rule and the formula for the size of a power set, there are 2^{n^{2}} possible directed graphs.

The number of permutations of an n-element set, P (n), is n!, which is bounded above and below by

(\frac{n}{e})^{n} ≤ n! ≤ (\frac{n + 1}{e})^{n+1} .

The number of entries in an n × n matrix is n^{2} by the product rule. Therefore, M(n), the number of n × n matrices with 0-1 entries, is 2^{n^{2}}

Putting all these facts together, we find that:

F_{n} = O(P (n))
P (n) = O(G(n))
G(n) = Θ(M(n))

Problem 7. (8 points) The inhabitants of Xoros 19 are unsatisfied with the performance of their Fritolator devices. They have constructed a factory to convert Fritolators into new, more deadly craft. Each day, the factory performs one of the following conversions:

1 Fritolator → 1 Pringlizer
2 Fritolators → 1 Tostitomatic
2 Fritolators → 1 Santitotron

Grzzwk, the ruler of Xoros 19, plans to use the factory to convert his entire fleet of n Fritolators. However, he must decide the sequence of ships that the factory will produce. Such a sequence is called a conversion schedule. For example, there are 5 possible conversion schedules for a fleet of n = 3 Fritolators:

1. Pringlizer, Pringlizer, Pringlizer

2. Pringlizer, Tostitomatic

3. Pringlizer, Santitotron

4. Tostitomatic, Pringlizer

5. Santitotron, Pringlizer

(a) (4 points) Let x_{n} be the number of possible conversion schedules for a fleet of n Fritolators. Express x_{n} with a recurrence relation and sufficient base cases.

If n = 0, then there is a single conversion schedule; namely, produce nothing. If n = 1, then there is still only one conversion schedule; the factory must produce a Pringlizer. If n ≥ 2, then every conversion schedule is one of the following:

1. A Pringlizer followed by a conversion schedule for n − 1 Fritolators.

2. A Tostitomatic followed by a conversion schedule for n − 2 Fritolators.

3. A Santitotron followed by a conversion schedule for n − 2 Fritolators.

Thus, for a fleet of n ≥ 2 Fritolators, there are x_{n−1} +2x_{n−2} conversion schedules. In summary:

x_{0} = 1
x_{1} = 1
x_{n} = x_{n−1} + 2x_{n−2} (for n ≥ 2)

(b) (4 points) Find a closed-form expression for x_{n}, the number of conversion schedules for a fleet of n Fritolators.

The characteristic equation is r^{2} −r −2 = 0. The roots of this equation are r = 2 and r = −1. The general form of the solution is therefore

x_{n} = A2^{n} + B(−1)^{n}

Substituting the base cases into this general form gives two linear equations:

1 = A + B
1 = 2A − B

The solution to this system of equations is A = \frac{2}{3} and B = \frac{1}{3}. Plugging these constants back into the general form of the solution gives the exact solution:

x_{n} = \frac{2}{3} · 2^{n} + \frac{1}{3} · (−1)^{n}

Problem 8. (10 points) Solve the following recurrence problems.

(a) (5 points) Find a closed-form solution to the following recurrence equation.

y_{0} = 0
y_{1} = 1
y_{n} = 7y_{n−1} − 12y_{n−2} + 1 (for n ≥ 2)

The characteristic equation is r^{2} − 7r + 12 = 0. The roots of this equation are r = 3 and r = 4. Therefore, the solution to the homogenous equation has the form:

y_{n} = A3^{n} + B4^{n}

The inhomogenous term is a constant, so we first guess a constant particular solution. Setting y_{n} = c gives:

c = 7c − 12c + 1
6c = 1
c = \frac{1}{6}

The complete solution has the form:

y_{n} = A3^{n} + B4^{n} + \frac{1}{6}

Substituting the base cases into this general form gives a system of linear equations:

0 = A + B + \frac{1}{6}
1 = 3A + 4B + \frac{1}{6}

The solution to this system is A = −\frac{3}{2} and B = \frac{4}{3}. The complete solution to the inhomogenous recurrence is therefore:

y_{n} = −\frac{3}{2} · 3^{n} + \frac{4}{3} · 4^{n} + \frac{1}{6}

(b) (5 points) Give a Θ bound on the solution to the following recurrence. For reference, ln 7 ≈ 1.9 and ln 8 ≈ 2.1.

T (n) = 8T (\frac{7n}{8}) + n\sqrt{n}

We use Akra-Bazzi. First, we find p.

8 · (\frac{7}{8})^{p} = 1
8 · 7^{p} = 8^{p}
ln 8 + p ln 7 = p ln 8
p = \frac{ln 8}{ln 8 − ln 7}
= 15.572 …

An integration gives the Θ bound:

T (n) = Θ (x^{p} · (1 + ∫_{1}^{x} \frac{u^{3/2}}{u^{p+1}} du))
= Θ (x^{p} · (1 + u^{3/2−p}))
= Θ (x^{p})

The final step uses the fact that p ≥ \frac{3}{2}.

Problem 9. (5 points) Suppose that we have functions f : A ↦ B, g : B ↦ C, and h : C ↦ A such that for all a ∈ A, h(g(f(a))) = a, and for all b ∈ B, f(h(g(b))) = b. Proofs are not required for any part of this problem.

(a) (1 points) Which of the functions f, g, and h must be injective?

The functions f and g must injective.

(b) (1 points) Which of the functions f, g, and h must be surjective?

The functions f and h must be surjective.

(c) (2 points) Circle the relations that must hold.

\begin{matrix}|B| > |C| & \underline{|C| ≥ |A|} & \underline{|B| ≤ |C|} \\ \underline{|A| = |B|} & |A| ≠ |C| & |A| + |B| ≥ |C| \end{matrix}

(d) (1 points) If g is surjective, then which of the functions f, g, and h must be bijective?

If g is surjective, then all of the functions must be bijective.

Problem 10. (10 points) Indicate whether each of the following sets is finite (F), countably infinite (CI), or uncountably infinite (UI) by circling the right answer. Note that an even quantity is necessarily finite.

6.042J/18.062JMidterm Solutions 11

The set of all binary strings with even length.  F \underline{CI} UI
The set of all infinite binary strings with 1’s in every even position. F CI \underline{UI}

(Odd positions may contain either a 0 or a 1.)

The set of all infinite binary strings with an even number of 1’s.  F \underline{CI} UI
The set of even primes.  \underline{F} CI UI
The set of all even-size sets of even-length binary strings.  F \underline{CI} UI

Problem 11. (6 points) The Pigeonhole Principle can be used to prove each of the following statements. In each case, say what the pigeons are, what the holes are, and what the function is that maps pigeons to holes. Example. If I pick five cards from a deck, then I will have at least two cards from some suit. Pigeons: The five cards. Holes: The four suits. Function: A card is mapped to its suit.

(a) (2 points) If everyone in an n-player tournament wins at least one match, then there must be two players with the same number of wins. Pigeons: The n players in the tournament. Holes: The numbers 1, 2, …, n − 1 Function: A player is mapped to the number of matches that he or she won.

(b) (2 points) This afternoon, 19 pigeons flew through 32 holes in a fence in such a way that at least one pigeon flew through each of the holes. Therefore, some pigeon flew through at least two holes. Pigeons: 32 holes Holes: 19 pigeons Function: A hole is mapped to the first pigeon that flew through it.

(c) (2 points) In any collection of six different, non-empty subsets of {a, b, c, d, e}, there exist two sets that intersect.

Pigeons: The six different, non-empty subsets.

Holes: The elements a, b, c, d, and e.

Function:

A subset is mapped to the first element in the list a, b, c, d, e that it contains.

Problem 12. (8 points) You might be interested to know that 42 students in the class have formed a new living group— 042 House— for students who especially enjoy 6.042 and want to talk about it all the time, even when they are at home. For this problem, your solutions may be expressions.

(a) (4 points) So far at 042 House there have been three meetings, which house members refer to as a, b, and c. (That’s the kind of people they are.) The secretary recorded the following attendance information.

• 34 attended meeting a

• 32 attended meeting b

• 30 attended meeting c

• 28 attended meetings a and b

• 27 attended meetings a and c

• 26 attended meetings b and c

• 25 attended meetings a, b, and c

How many house members punted all three meetings?

Let A, B, and C denote the sets of people that attended meetings a, b, and c. The number of people that attended at least one meeting is |A ∪ B ∪ C|. We can compute this quantity with the Inclusion-Exclusion Principle:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
= 34 + 32 + 30 − 28 − 27 − 26 + 25
= 40

Since 40 people attended at least one meeting, two people punted all three meetings.

(b) (2 points) The 042 House is about to have its first wild party. They have identified 23 distinct preparatory chores, such as working out a good mix of practice problems to entertain the guests. One student must be assigned to each chore, and no student can be assigned to two or more chores. In how many ways can students be assigned to chores?

This is the number of 23-permutations of a 42-element set, which is 42!/19!.

(c) (2 points) Theory Pig has decided to visit the living group for 30 days, provided that one student attend to his needs each day. A student may attend to Theory Pig any number of times. In how many ways can the sequence of attendants be chosen?

There are 42 possible attendants each day. By the product rule, there are 42^{30} possible sequences of attendants.