Massachusetts Institute of Technology Final Exam Solutions 6.042J/18.062J: Mathematics for Computer Science May 15 2000 Professors David Karger and Nancy Lynch

Final Exam Solutions

6.042J/18.062J Final Exam Solutions  2  Name:

[induction2]

Problem 1 [12 points] Source: s99 ps3

Topics: Induction, Graphs, Recursive Definitions

This problem concerns Hamiltonian paths in n-cubes. A Hamiltonian path in a graph is a path traversing every vertex in the graph exactly once. An n-cube is defined recursively as follows: A 0-cube is a single vertex. An (n+1)-cube consists of two n-cubes with corresponding vertices joined by edges. For example, a 2-cube (a square) is two 1-cubes (line segments) with their ends joined. (Hamiltonian paths and n-cubes are also defined in Rosen.)

(a) [2 points] Draw a 3-cube, distinguishing between the edges forming the 2-cubes and the edges joining those two 2-cubes together (e.g., using solid lines for one and dashed lines for the other).

Solution This is a simple drawing of a cube, with 2 opposing squares drawn in a different style.

(b) [2 points] In your drawing, highlight a Hamiltonian path.

Solution This can be drawn by tracing three sides of one of the squares, crossing over, tracing three sides of the oposing square, and returning.

(c) [8 points] Use induction to prove that an n-cube has a Hamiltonian path for all n ∈ ℕ.

Solution The proof is by induction. Let P (n) be the proposition that an n-cube has a Hamiltonian cycle. In the base case, P (2) is true, because a 2-cube is itself a cycle.

In the inductive step, assume that an n-cube has a Hamiltonian cycle to prove that an (n + 1)-cube has a Hamiltonian cycle. Regard an (n+1)-cube as two n-cubes with corresponding vertices joined. The first n-cube has a Hamiltonian cycle H by induction, and there is a matching Hamiltonian cycle H′ in the second n-cube.

Take an edge (u, v) ∈ H and the corresponding edge (u′, v′) ∈ H′. We can construct a Hamiltonian cycle in the (n + 1)-cube by starting at vertex u, traversing the cycle H all through the first n-cube until reaching vertex v, crossing the edge (v, v′), traversing the cycle H′ all through the second n-cube until reaching vertex u′, and then crossing the edge (u′, u).

[wellordering1]

Problem 2 [5 points] Source: f95 ps3

Topics: Well Ordering (gcd, lcm)

The least common multiple of two natural numbers m and n is defined to be the smallest natural number k such that m|k and n|k. It is denoted by lcm(m, n). Using well-ordering, prove that every pair of natural numbers has a least common multiple.

Solution Let m and n be any two natural numbers. Let M be the set of multiples of m and N the multiples of n. Consider M ∩ N. It is nonempty since it contains mn. By the well-ordering principle it contains a least element which is the least common multiple of m and n. Hence every pair of natural numbers has a least common multiple.

[induction7]

Problem 3 [8 points] Source: s97 ps3

Topics: False Proofs, Well Ordering, Induction

Find the flaws in the following “proofs;” circle the step in which an error was made, and explain the problem.

(a) [4 points] CLAIM: a^{n} = 1 for all nonnegative integers n, whenever a is a nonzero real number.

BASIS STEP: a^{0} = 1 is true by the definition of a^{0}.

INDUCTIVE STEP: Assume that a^{k} = 1 for all nonnegative integers k with k ≤ n. Then

a^{n+1} = \frac{a^{n} · a^{n}}{a^{n−1}} = \frac{1 · 1}{1} = 1.

Solution The flaw is that we should prove both n = 0 and n = 1 as bases cases because the inductive step uses the previous two values of n. Clearly a^{1} = 1 is not true, unless a = 1, and therefore the proof is wrong.

(b) [4 points] CLAIM: \sqrt{2} is rational.

PROOF: By well-ordering. Let S be the set of all rational numbers greater than or equal to \sqrt{2}. This set contains a least element r by well-ordering. If this element is not \sqrt{2}, then there is another rational element between \sqrt{2} and r (by denseness of the rationals), implying r is not the smallest, a contradiction. Thus we must have r = \sqrt{2}.

Solution The flaw is that the well-ordering principle does not hold for the rationals, so we cannot use it to conclude that the above set has a minimum. (Note that the problem is not that the set is infinite.)

[pigeonhole1]

Problem 4 [10 points] Source: Kyle’s brain, inspired by a trip to the Galleria

Topics: Pigeonhole principle

For their annual convention, the members of the MIT Antisocial League rent out the cafeteria at the CambridgeSide Galleria. The cafeteria is an n × n grid of cells, each cell containing exactly one table with a single associated chair. A chair can be positioned around its table to face in one of four directions, corresponding to the axes of the grid.

Every attendee sits in a chair at a table. Since this is the Antisocial League, no one sits directly facing an occupied table (i.e., there can be no one sitting at a table in a person’s direct line of sight). For example, each box below represents a 4 × 4 grid, and each arrow represents a person sitting at the table in that cell, and facing in the direction of the arrow.

The configuration on the left is legal: no one is directly facing anyone else. The configuration on the right is not legal, since the person in cell C3 is directly facing the person in C1.

(a) [5 points] Prove that if n + 1 people face in the same direction, the configuration is not legal.

(b) [5 points] Prove that there is no legal configuration if 4n + 1 members attend.

Solution We use the pigeonhole principle to prove the theorem. Orient a representation of the grid in some canonical way with one axis pointing left-right, and the other pointing up-down.

There are four directions in which people can face. As a result, by the generalized pigeonhole principle, at least n+1 people must be facing in some direction. Without loss of generality, assume this is downwards.

Create n pigeonholes from the columns of the grid. By the PP, if there are n + 1 attendees facing downwards, at least two must be in the same column, so clearly one must be directly facing another occupied table.

It is likely that equality is not achieved (which would be proved by demonstrating an arrangement of 4n people in which no one directly faced another occupied table). This suggests a stronger theorem can be proven. The best we can do so far is 4n − 4; try to figure out such a solution.

[recurrences3]

Problem 5 [10 points] Source: Kyle

Topics: Homogeneous/inhomogeneous LDE

One of the top ore-cum-food firms, Amalgamated Steel and Spice, has been receiving complaints based on the spreading rumor that one of its products—Happy-O’s with Nuts—actually has rusting iron filings instead of pecan shavings.

Mulder and Scully were sent in to investigate. With the help of (the suave) Langley and (the mighty) Frohike, they gathered enormous amounts of data concerning a conspiracy against the American people to hide the Truth behind this supposed “mistake.”

(a) [3 points] Our heroes find that a new complaint on any particular day generates one new complaint on the following day and six new complaints on the day after that. Write a recurrence for T (n), the number of new complaints on day n, that is valid for n ≥ 2.

Solution

T (n) = T (n − 1) + 6T (n − 2)

(b) [3 points] Give the general closed form of the solution to this recurrence.

Solution The characteristic equation is x^{2} − x − 6 = 0, whose roots are 3 and −2. The general solution is then of the form T (n) = A3^{n} + B(−2)^{n}. Now we solve for the constants by plugging in the initial conditions: 0 = 3A − 2B and 30 = 9A + 4B imply that A = 2 and B = 3. So, the final solution is

T (n) = 2 · 3^{n} + 3(−2)^{n}

(c) [3 points] Scully does some more digging and discovers that there are 30 additional new complaints filed spontaneously every day after the first. Give the new recurrence for T (n) that takes into account these additional complaints.

(d) [5 points] There are no complaints on day 0, and just 30 complaints on day 1 (i.e., T (0) = 0 and T (1) = 30). Solve the recurrence in part (c), giving a closed-form solution to it.

Solution The general solution to the inhomogeneous part remains as before; now, however, we have the initial conditions T (1) = 6 and T (2) = 42, and an inhomogeneous part n. We guess a linear solution an + b, and plug in the initial conditions:

an + b = an + b + 6(an + b) + 6n
0 = (6a + 6)n + 6b

So 6a + 1 = 0 ⇒ a = −1 and 6b = 0 ⇒ b = 0 for our particular solution −n. So, we plug in and solve for the constants:

T (1) = 6 = 3A − 2B − 1
T (2) = 42 = 9A + 4B − 2

The solutions to this system are A = 58/15 and B = 23/10. So, our complete solution is

T (n) = (58/15)3^{n} + (23/10)(−2)^{n} − n

6.042J/18.062J Final Exam Solutions  8  Name:

[statemachines1]

Problem 6 [12 points] Source: Nancy

Topics: State machines, graphs

Consider a state machine whose state is a directed graph with vertex set V = {1, 2, 3, 4, 5}. The transitions of the state machine are:

• add-out(a,b) (a, b distinct vertices): Can occur if a has no incoming edges and the edge a ⟶ b is not in the graph. Effect is to add the edge a ⟶ b.

• add-in(a,b) (a, b distinct vertices): Can occur if a has no outgoing edges and the edge b ⟶ a is not in the graph. Effect is to add the edge b ⟶ a.

• trans(a,b,c) (a, b, c distinct vertices): Can occur if the edges a ⟶ b and b ⟶ c are in the graph, but a ⟶ c is not. Effect is to add the edge a ⟶ c.

Initially, the state is that of the “line graph” (1 ⟶ 2 ⟶ 3 ⟶ 4 ⟶ 5).

(a) [6 points] Define a function that can be used to prove that this state machine eventually halts, and argue that the function satisfies the properties of a termination function.

Solution f(n) = n(n − 1) − #edges is such a termination function. Without remove and reverse, every transition adds an edge to the graph, decreasing this function. When no transition is possible, the graph must be transitively closed, because we have an explicit transitive-closure step.

Now consider the state machine with the following additional transitions:

   • remove(a,b) (a, b vertices):

Can occur if there is an edge from a to b.

Effect is to remove the edge.

   • reverse(a) (a vertex):

Can occur if either all the edges incident upon a are incoming, or all are outgoing.

Effect is to reverse the direction of all edges incident on a.

(b) [6 points] Consider the graph that is the same as the line graph above, but with the additional edge 5 ⟶ 1. Is this state reachable from the initial state (the line graph)? If so, give an execution that reaches it. Otherwise, state and argue the correctness of an invariant that can be used to show that the state cannot be reached. Your invariant must be provable by induction (or the Invariant Theorem), though you do not have to prove it formally.

Solution Not reachable. The invariant is that the graph is always acyclic. Suppose for contradiction that applying a rule made a graph have a cycle. Then that cycle must involve the nodes affected by the rule, because nothing else changed. Thus, there must be a path from a to some node x and from x to a. However, the remove(r)ule certainly will not create cycles, and the add(a)nd reverse(r)ules will leave a with only incoming or only outgoing edges. Thus, both paths cannot exist. The trans(r)ule will only add an edge from a to a node that was reachable from a already, so any cycle containing the new edge could have been made before with the old path in place of the new edge (a contradiction).

You could also state the invariant that no node may have both in and out edges (unless it did in an input graph).

[indep1]

Problem 7 [10 points] Source: Kyle

Topics: Mutual independence

Consider three random variables, A, B, C, each of which takes on either −1 or 1 independently with uniform probability, and a fourth random variable D = A · B · C.

(a) [5 points] Show that these four random variables are not mutually independent.

Solution

Pr ( A = 1 ) = \frac{1}{2}
Pr ( A = 1 | B = 1, C = 1, D = 1 ) = 1

The conditional probability is not equal to the unconditional probability.

(b) [5 points] Show that any three of these variables are mutually independent.

Solution A, B, C are given as independent. D, A, and B are independent because a simple table shows their probabilities of being 1 as all \frac{1}{2}, both unconditional and conditioned on values of the other two.

Basically, fix any two of these three variables. Then, the value of C will make the unfixed variable either 1 or −1. Since C has a uniform distribution, the unfixed variable must also have a uniform distribution, conditioned on the other two. (It actually remains to be shown that D has a uniform distribution in the unconditional case, but this can be easily seen by counting or other arguments.)

6.042J/18.062J Final Exam Solutions  11  Name:

[diagnosis1] Problem 8 [12 points] Source: Nancy Topics: Probability It was reported in last Sunday’s paper that 1/1000 of the population are estimated to have a newlydiscovered chronic illness called Creeping Rot Disease. We don’t know what it is, but it doesn’t sound good. Luckily, a new test for Creeping Rot (CR) has become available. If a person has CR, the test is 80% accurate in diagnosing it. Similarly, if the person does not have CR, the test says so 80% of the time.

(a) [4 points] What is the probability that a person chosen randomly tests positive for CR? Solution

Pr(T) = Pr(T |CR) Pr(CR) + Pr(T |\overline{CR}) Pr(\overline{CR})
= (.8)(.001) + (.2)(.999)
= .2006

(b) [4 points] If a randomly chosen person gets a positive test result, what is the probability that he or she has CR? Solution

Pr(CR|T) = Pr(T |CR) Pr(CR)/ Pr(T)
= (.8)(.001)/(.2006)

Approx. .004

(c) [4 points] If the person gets a negative test result, what is the probability that he or she has CR? Solution

Pr(CR|\overline{T}) = Pr(\overline{T} |CR) Pr(CR)/ Pr(\overline{T})
= (1 − Pr(T |CR)) Pr(CR)/(1 − Pr(T))
= (.2)(.001)/(.7994)

Approx. .00025

6.042J/18.062J Final Exam Solutions  12  Name:

[expectation1] Problem 9 [12 points] Source: Nancy’s brain Topics: Expectation, linearity of expectation, expected number of events that occur, binomial distribution, counting permutations Five students in 6.042 each choose a number from {1, 2, 3, 4, 5}, randomly and independently, using the uniform distribution.

(a) [3 points] What is the expected number of people who choose the number that gives their position in alphabetical order? Justify your answer. Solution 1

(b) [3 points] Evaluate the probability that exactly one person chooses his or her correct position. You may leave your answer in terms of binomial coefficients. Solution \underbrace{\binom{5}{1}\frac{1}{5}}_{Winner} \underbrace{(\frac{4}{5})^{4}}_{Losers} Now suppose the five students are assigned numbers by their TA, who chooses the assignment uniformly from the set of permutations of {1, 2, 3, 4, 5}. (Each student is assigned a different number.)

(c) [3 points] Now what is the expected number of people who are assigned the number that gives their position in alphabetical order?

Solution 1

(d) [3 points] Give an expression for the probability that exactly one person is assigned his or her correct position.

Solution This is more complicated, and a little too ad hoc for my taste. Maybe need hints?

Definitely ad-hoc: but a tree diagram shows that way.

I calculate that there are 45 5-permutations in which exactly one guy is a ”fixed point”, which gives a probability of 45/120, or 3/8. To get the 45, I figure 5 choices for the fixed point, then 9 4-perms with no fixed point. But, to figure out that there are exactly 9 4-perms with no fixed point, I used slightly ad hoc arguments: 3 possibilities for who gets the number 1; then for each of these, say the guy with rank i, three possibilities for who gets the number i; after these two are assigned, it turns out that the final assignments have only one possibility.

In trying to generalize this, I got a somewhat messy recurrence. So I’m inclined just to leave it as an ad hoc calculation. OK since the numbers are very small. Or, we can give them the 9 as a hint.

I was hoping to get a comparison between these two experiments, but don’t see anything nice here. Is it clear which of the two kinds of experiments should yield the higher probability of getting exactly one fixed point? Here, the probability is higher in the case of the first experiment (.4096 vs. .375). In general?

6.042J/18.062J Final Exam Solutions  14  Name:

[wald1]

Problem 10 [10 points] Source: victor Topics: Wald’s theorem A miner, lost in some abandoned mine, finds himself in a room containing three doors. Door 1 leads him to freedom after two hours travel; door 2 returns him to the same room after four hours travel, and door 3 returns him to the room after eight hours travel. Each time he finds himself in the room, the miner picks a door with equal probability. Let T denote the number of hours until he finds the exit.

(a) [5 points] Define a sequence of independent, identically-distributed random variables X_{i} and a non-negative, integer-valued random variable N such that

T = ∑_{i=1}^{N} X_{i}

Solution We view this as an experiment where at each step we make a choice between three equiprobable outcomes. Let X_{i} = number of hours to return to room on ith step. Let N = number of steps until good door is selected. Then N is geometrically distributed with probability 1/3.

(b) [5 points] Find E[T]. Justify your answer.

Solution Pr(X_{i} = 2) = 1/3 Pr(X_{i} = 4) = 1/3 Pr(X_{i} = 8) = 1/3 E[X_{i}] = 14/3 E[N] = 3 By Wald’s Theorem,

E[∑_{i=1}^{N} X_{i}] = 14

6.042J/18.062J Final Exam Solutions  15  Name:

[markov1] Problem 11 [15 points] Source: Nancy Topics: Markov and Chebyshev Bounds The average IQ of all MIT faculty is exactly 150. No MIT faculty has negative IQ (those are at Harvard).

(a) [3 points] Give a tight upper bound on the probability that a random MIT faculty member’s IQ is 175 or more. Solution Use Markov, get ≤ 150/175 = 6/7

(b) [3 points] Give an example distribution of IQ’s that shows your bound in part (a) is tight. Solution 6 faculty members with IQ 175, one with IQ 0.

(c) [3 points] Suppose that no MIT faculty member has IQ below 100. How can you tighten the bounds proven in the first part? Solution Recenter the Markov “zero” around 100.

6.042J/18.062J Final Exam Solutions  16  Name:

(d) [3 points] Now suppose that the standard deviation of IQ’s of MIT faculty members is 15. Give a tight upper bound on the probability that a random MIT faculty member’s IQ is above 175 or below 125, taking this new information into account. Solution Use Chebyshev

(e) [3 points] Give an example distribution of IQ’s that shows your bound in part (d) is tight. Solution LTTR

6.042J/18.062J Final Exam Solutions  17  Name:

[pmethod1] Problem 12 [14 points] Source: Nancy Topics: Probabilistic Method In a round-robin tournament with n players, consider the question of whether there is a possible tournament outcome (i.e., a tournament digraph) in which every player wins at least two matches (i.e., every node in the digraph has at least two outgoing edges).

(a) [3 points] Suppose each match is equally likely to be won by either player, and all matches are mutually independent. What is the probability that a particular player wins at most one game? Solution \frac{n}{2^{n−1}} , since there are n ways to win no more than one game—1 way to win zero, n − 1 ways to win 1 versus n − 1 opponents—out of 2^{n−1} possible ways to win/lose n − 1 games.

(b) [3 points] Give an upper bound for the probability that some player wins at most one game. Solution By the union bound, this is just \frac{n^{2}}{2^{n−1}} .

(c) [2 points] Give a lower bound for the probability that all players win at least two games. Solution This is just the complement of the previous part, so 1 − \frac{n^{2}}{2^{n−1}} .

6.042J/18.062J Final Exam Solutions  18  Name:

(d) [2 points] Give a condition that implies a positive probability of all players winning at least two games. Solution 1 − \frac{n^{2}}{2^{n−1}} > 0.

(e) [4 points] Explain briefly why your condition implies the existence of such a tournament. Solution If there is a non-zero probability of such an event occurring, then there must be a configuration in which that event occurs.

[combinatorics1]

Problem 13 [10 points] Source: Nancy’s brain

Topics: Combinatorics

For a nonempty set S, prove that the number of even-sized subsets is equal to the number of oddsized subsets by constructing a bijection between the even-sized subsets and the odd-sized subsets. (An algebraic proof of this fact will not be accepted.)

Hint: Fix an arbitrary element of S, and consider whether each subset contains it or not.

Solution Our mapping f : E → O complements the presence of some arbitrary element in the input set; i.e., choose some element e ∈ S so that f(X) = X ∪ {e} if e ∉ X, or f(X) = X − {e} if e ∈ X. We must prove the function is defined on its domain, is one-to-one, and is onto.

|X| even-sized ⇒ |f(X)| odd-sized. Clearly |f(X)| = |X| ± 1, so if X is even-sized, then f(X) is odd-sized.

f one-to-one. Assume f(X) = f(Y). If e ∉ f(X) and e ∉ f(Y), then X = f(X) ∪ {e} and Y = f(Y) ∪ {e}, so X = Y; otherwise, if e ∈ f(X) and e ∈ f(Y), then X = f(X) − {e} and Y = f(Y) − {e}, so again X = Y.

f onto. Consider an odd-sized set Y: if e ∉ Y, then |Y ∪ {e} | is even-sized, so f(Y ∪ {e}) = Y; otherwise, if e ∈ Y, then |Y − {e} | is even-sized, so f(Y − {e}) = Y.

Have a great summer!!!