Massachusetts Institute of Technology Practice Final Exam 6.042J/18.062J: Mathematics for Computer Science November 30 2000 Professors Nancy Lynch and Srinivas Devadas

Practice Final Exam

6.042J/18.062J Practice Final Exam  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. The n-cube is defined on page 448 of Rosen (p. 441 in ed. 3). (Rosen also uses the name Q_{n} for an n-cube.) However, the following recursive definition of an n-cube is equivalent to the one given in Rosen, but may simplify your solutions. 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 standard cube (here, called a 3-cube) is two squares with corresponding corners joined.

(a) Draw a 4-cube. [2 points]

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

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

The proof is by induction. Let P (n) be the proposition that an n-cube has a Hamiltonian path. 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 path to prove that an (n + 1)-cube has a Hamiltonian path. Regard an (n + 1)-cube as two n-cubes with corresponding vertices joined. The first n-cube has a Hamiltonian path H by induction, and there is a matching Hamiltonian path H′ in the second n-cube.

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

6.042J/18.062J Practice Final Exam  3  Name:

[induction7]

Problem 2 [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 note that a^{n+1} = \frac{a^{n}·a^{n}}{a^{n−1}} = \frac{1·1}{1} = 1. 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: 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}. 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.

[wellordering1]

Problem 3 [10 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).

(a) [5 points] Using well-ordering, prove that every pair of natural numbers has a least common multiple.

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.

(b) [5 points] Say a = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{n}^{α_{n}} and b = p_{1}^{β_{1}}p_{2}^{β_{2}} ⋯ p_{n}^{β_{n}} where the p_{i} are prime and the α_{i} and β_{i} are non-negative (i.e., possibly zero). Express the least common multiple of a and b in terms of these prime factorizations of a and b.

Let a = ∏_{i}p_{i}^{α_{i}} and b = ∏_{i}p_{i}^{β_{i}} where p_{1}, p_{2} … are the primes in increasing order. Following Theorem 7.12

in Handout 13, Notes 4, it was shown that gcd(a, b) = ∏_{i}p_{i}^{min(α_{i},β_{i})}. By an identical argument it can be seen

that lcm(a, b) = ∏_{i}p_{i}^{max(α_{i},β_{i})}. Now, from the fact that for any α and β, α + β = max(α, β) + min(α, β), it follows that a · b = gcd(a, b) · lcm(a, b).

[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 and 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.

Due to space considerations, every attendee must sit at a chair. But, since this is the Antisocial League, no seated person can directly face another occupied table (i.e., there can be no one sitting at a table in a person’s direct line of sight). Use the pigeonhole principle to prove that this requirement cannot be satisfied if 4n + 1 members attend.

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 [12 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.

During the time in which the X-Files were closed, Mulder and Scully were sent in to investigate. With the help of (the suave) Langley and (the mighty) Frohike, they were able to gather enormous amounts of data concerning a conspiracy against the American people to hide the Truth behind this supposed “mistake.”

(a) [2 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 T (n) valid for n ≥ 3 that represents the number of new complaints on day n.

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

(b) [4 points] On day 1, 0 complaints are generated; on day 2, 30 complaints are generated (i.e., T (1) = 0 and T (2) = 30). Find a closed form for the recurrence in the previous part.

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) [6 points] Scully does some more digging and notices that 6n additional complaints are filed spontaneously on day n for n ≥ 1. Find new initial conditions based on this new information, show an inhomogeneous recurrence, and find a closed-form solution to it.

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 Practice Final Exam  8  Name:

[statemachines1]

Problem 6 [12 points] Source: Nancy

Topics: State machines, graphs

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

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

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

• trans(a,b,c) (a, b, c distinct vertices): Can occur if there is an edge from a to b and another from b to c. Effect is to add the edge a ⟶ c.

(a) [6 points] We want to prove that, eventually, a transitively closed graph is produced. Assume that we are considering a “live” execution, i.e. one that does not stop as long as some transition is possible.

Define a termination function that can be used to prove this eventuality property. Argue that it satisfies the properties of a termination function.

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.

6.042J/18.062J Practice Final Exam  9  Name:

Consider adding the following transitions to our state machine:

   • 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.

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

(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? If it is, then describe an execution that reaches it; otherwise, state an invariant that can be used to show that the state cannot be reached. Such an invariant must be provable by induction (or the Invariant Theorem). Instead of giving a proof of the invariant, just state key reasons.

Not reachable. The invariant is that the graph in the state is always acyclic.

6.042J/18.062J Practice Final Exam  10  Name:

[combinatorics1]

Problem 7 [10 points] Source: Nancy’s brain Topics: Combinatorics Prove combinatorially that the number of even-sized subsets of a set S ≠ ∅ is equal to the number of oddsized subsets. Formally, denoting by E the even-sized subsets of S and by O the odd-sized subsets of S, construct a bijection between E and O. An algebraic proof will not be accepted. Hint: Although there is a natural bijection that works for all S, you may find it clearer to divide the bijection into one that works for even-sized S and one that works for odd-sized S. 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.

[expectation1]

Problem 8 [12 points] Source: Nancy’s brain

Topics: Expectation, linearity of expectation, expected number of events that occur, binomial distribution, counting permutations

Each of 5 students in 6.042 chooses a natural number in the range [1, …, 5], randomly and independently, using the uniform distribution on [1, …, 5].

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

1

(b) [3 points] Give an expression representing the probability that exactly the expected number of people (as given by your answer to the previous part) choose their correct positions.

\underbrace{\binom{5}{1}\frac{1}{5}}_{Winner} \underbrace{(\frac{4}{5})^{4}}_{Losers}

Now suppose the 5 students are all assigned numbers in the range [1, …, 5] by a course TA, who chooses randomly from the uniform distribution on permutations of [1, …, 5].

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

1

(d) [3 points] Give an expression for the probability that exactly the expected number of people (as given by your answer to the previous part) are assigned their correct positions.

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

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 Practice Final Exam  13  Name:

[wald1]

Problem 9 [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 time until he finds the exit.

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

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

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] Use Wald’s Theorem to find Ex[T] Pr(X_{i} = 2) = 1/3 Pr(X_{i} = 4) = 1/3 Pr(X_{i} = 8) = 1/3 Ex[X_{i}] = 14/3 Ex[N] = 3 By Wald’s Theorem,

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

6.042J/18.062J Practice Final Exam  14  Name:

[markov1]

Problem 10 [12 points] Source: Nancy Topics: Markov and Chebyshev Bounds The average IQ of all MIT faculty is known to be exactly 150.

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

(b) [3 points] Give an example distribution of weights showing that your bound in the first part is tight. 6 faculty members with IQ 175, one with IQ 0. Now assume also that the standard deviation of IQs of MIT faculty members is 25.

(c) [3 points] Give a tight upper bound on the probability that a random MIT faculty member’s IQ is 175 or more, taking this new information into account. Use one-sided Chebyshev

(d) [3 points] Give an example distribution of weights showing that your bound in the previous part is tight. LTTR [pmethod1]

Problem 11 [14 points] Source: Nancy

Topics: Probabilistic Method

Consider n players in a round-robin tournament. We are going to consider the question of whether there exists a possible tournament outcome (that is, a tournament digraph) in which every player wins at least two matches (that is, every node in the digraph has at least two outgoing edges). We would like you to use the probabilistic method to show that such an outcome exists, for certain values of n.

(a) [3 points] Say a match between two players—a and b—is won by a with probability 1/2 and by b with probability 1/2. What is the probability that a particular player wins no more than one game?

\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] Now, upper bound the probability that some player wins no more than one game.

By the union bound, this is just \frac{n^{2}}{2^{n−1}} .

(c) [2 points] Lower bound the probability that all players win at least two games.

This is just the complement of the previous part, so 1 − \frac{n^{2}}{2^{n−1}} .

6.042J/18.062J Practice Final Exam  16  Name:

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

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

6.042J/18.062J Practice Final Exam  17  Name:

[indep1] Problem 12 [12 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) [6 points] Show that any three of these variables are mutually independent, but all four are not.

(b) [6 points] Extend this theorem to n independent random variables X_{1}, …, X_{n} over the same distribution and their product Y = ∏_{i=1}^{n} X_{i}, and argue its correctness. TBD

6.042J/18.062J Practice Final Exam  18  Name:

[intransitivity1] Problem 13 [10 points] Source: Kyle and Nancy Topics: Intransitivity of probability Consider four 4-sided dice (labelled A, B, C, and D), each with four unique digits from 1 through 16:

A: 1 8 11 14
B: 2 5 12 15
C: 3 6 9 16
D: 4 7 10 13

Die x is said to beat die y on a particular roll if x comes up with a higher roll than y.

(a) [5 points] Calculate Pr(B beats A), Pr(C beats B), Pr(D beats C), and Pr(A beats D). • P r(B beats A) = 1/16 + 1/16 + 3/16 + 4/16 = 9/16

• P r(C beats B) = 1/16 + 2/16 + 2/16 + 4/16 = 9/16

• P r(D beats C) = 1/16 + 2/16 + 3/16 + 3/16 = 9/16

• P r(A beats D) = 0/16 + 2/16 + 3/16 + 4/16 = 9/16 Consider the binary relation R(x, y) on dice that indicates whether P r(x beats y) > P r(y beats x). A relation is said to be a strict partial order if it satisfies the requirements for being a partial order except that it is not reflexive. (For instance, < on the natural numbers is a strict partial order, while ≤ on the same set is a partial order.)

(b) [5 points] Is R a strict partial order? Prove your answer. No, it is not transitive; clearly R(D, C), R(C, A), and R(B, A), but ¬R(D, A).

[diagnosis1]

Problem 14 [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 newly-discovered 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 has become available. If a person has C.R., the test is 80% accurate in diagnosing it. On the other hand, if the person does not have C.R., the test has only a 20% probability of a ”false positive”.

(a) [4 points] If the test is given to a random person in the population, then what is the probability that it comes out positive?

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

(b) [4 points] If a person gets a positive test result, then what is the probability that he actually has C.R.?

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

Approx. .004

(c) [4 points] If a person gets a negative test result, then what is the probability that he has C.R.?

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. .0025