Final Exam Solutions

Problem 1 [33 points] Miscellaneous

(a) (6 points) Circle the numbers of ALL of the following which are logical tautologies:

1. (P ∧ ¬P) ∨ (Q ∨ ¬Q)

2. (P ⇔ Q) ∨ (¬P ∨ Q)

3. ∀x∀y(P (x) ∧ ¬P (x)) ⇒ Q(y)

Solution: 1 and 3 are tautologies and 2 is not.

In 1, (Q ∨ ¬Q) is always true. Since it is one part of an or expression, the law of domination tells us the expression is always true.

In 2, the expression is false if P is true and Q is false.

In 3, the expression P (x) ∧ ¬P (x) is always false. Since an implication is always true if its antecedent is false, the expression (P (x) ∧ ¬P (x)) ⇒ Q(y) is true for all x and y.

(b) (3 points) Define the relation R such that nRm whenever n and m are natural numbers such that |n − m| is the square of a nonnegative integer. Circle the numbers of ALL of the following which apply to R:

1. A reflexive relation

2. A symmetric relation

3. An equivalence relation

Solution: 1 and 2 apply to R but 3 does not.

Since 0 is a nonnegative integer, 0 is the square of a nonnegative integer. Thus, if n = m, then |n − m| = 0 so nRm. Thus, 1 applies.

If |n−m| = a where a is the square of a nonnegative integer, then |m−n| = |(−1)(n−m)| = a, so mRn. Thus, 2 applies.

However, 0R1 and 1R5 but ¬0R5, so R is not transitive. Thus, 3 does not apply.

(c) (10 points) Circle the numbers of ALL of the following statements that are true for all m, n > 0 ∈ N. Let G be an m by n grid graph.

1. There is an Euler circuit in G.

2. There is a Hamiltonian path in G.

3. If m and n are even, there is a Hamiltonian circuit in G.

4. If m and n are odd, there is a Hamiltonian circuit in G.

5. If there is a Hamiltonian circuit in G then m and n are even.

Solution: 2 and 3 are true; the others are false.

1 is not true if either m or n is not equal to 2. Thus is it not true for ALL m and n, though it is true for some.

2 is true. The Hamiltonian path simply goes row by row and snakes back and forth.

3 is true. We proved a less general version of this on the first exam; the proof is analagous.

4 is false. Grid graphs are 2-colorable; however, a Hamiltonian circuit contains every node once. Thus, since mn is odd, the Hamiltonian circuit is a circuit of odd length that is 2-colorable. This is not possible, so there could be no Hamiltonian circuit.

5 is false. Actually, the accurate statement is that if there is a Hamiltonian circuit in G then either m or n is even. The 2 by 3 grid graph gives a counterexample to 5.

(d) (8 points) Circle the numbers of ALL of the following functions which are θ(n):

1. f(n) = 8000\sqrt{n} + .00034n

2. g(n) = \frac{n^{2}+3n−4}{−4n^{2}+9n+9}

3. h(n) = log(n!/n)

4. l(n) = n^{1+ \frac{1}{n}}

Solution: 1 and 4 are θ(n).

1: f(n) is clearly θ(n) since the growth of n outstrips that of \sqrt{n}.

2: g(n) is O(n) but not Ω(n) since lim_{n→∞} g(n) = −\frac{1}{4}.

3: h(n) is Ω(n) but not O(n). By Stirling’s approximation, log(n!) = θ(n log n). Thus, h(n) = θ(n log n − n) which is still θ(n log n).

4: l(n) is clearly greater than n, so it is Ω(n). However, the other direction is harder. The question becomes whether there is a constant c such that for sufficiently large n,

n^{1+ \frac{1}{n}} < cn

n^{\frac{1}{n}} < c

\frac{1}{n} log n < log c

which is true for (say) c = e since lim_{n→∞} \frac{1}{n} log n = 0. Thus, l(n) = O(n), so l(n) = θ(n).

(e) (6 points) Circle the numbers of ALL of the following which are uncountably infinite sets:

1. The set of all even natural numbers

2. The set of all subsets of the even natural numbers

3. The set of all real numbers with only even digits in their decimal representations

Solution: 2 and 3 are uncountably infinite, but 1 is not.

1 is clearly countable. 0, 2, 4, … is the way to count it.

2 is uncountable by the standard diagonalization argument. It is just like P(ℕ).

3 is uncountable. The diagonalization argument for the uncountability of the real numbers works even better here, since we don’t run into the .9999 … = 1 issue.

Problem 2 [16 points] Counting Connected Components of a Graph

Consider the following algorithm, which counts the number of connected components in a graph by “contracting” edges until there are no edges left in the graph.

CompCount (Undirected Graph G)

1. H := G

2. While H contains at least one edge do:

1. Pick an edge (v, w) in H.

2. Add a new vertex z to H.

3. For each vertex p in the graph, add the edge (p, z) to H if and only if (p, v) or (p, w) is an edge in H.

4. Remove vertices v, w and all their incident edges from H.

3. n := the number of vertices in H.

4. CompCount (G) := n

(a) (3 points) If H is the graph given below, and the edge (v, w) is the one selected in step 2.1, draw the graph H after step 2.4 in the algorithm. Label the z vertex in your graph.

Solution:

(b) (3 points) Model this algorithm as a state machine.

Solution:

The states of the machine will be pairs (G, H) where G and H are graphs.

The start state q_{0} of the machine will be pairs (G, G) where G is some graph.

The transitions are of the form (G, H) ↦ (G, H′_{(v,w)}). They exist as long as H has any edges, and for each edge (v, w) in H there is a transition.

The graph H′ has all the same vertices as H, except that v and w are replaced by a single vertex z. The edges between vertices not involving v and w are in H′, and for any other vertex x, there is an edge between x and z in H′ if and only if there is an edge between x and v or between x and w in H.

(c) (7 points) Prove, using an invariant, that if the algorithm terminates, the output is the number of connected components of G. You may assume that in a graph with no edges, the number of connected components is equal to the number of vertices.

Solution:

Let our invariant P (q) be, “In state q, H has the same number of connected components as G.”

The invariant is clearly true in the start state, since H and G are the same graph.

Suppose that (G, H′_{(v,w)}) is a state reachable from (G, H). Since there is an edge from v to w they must be in a connected component. Clearly, all other connected components still exist in H′ so there is no problem. We must prove that those vertices corresponding to the connected component including v and w form a connected component in H′.

Suppose x is in the same connected component as v and w but x is different from both v and w. Then there is a path from x to v in H, so there is a path from x to z in H′. (To make it, simply reuse any edge not involving v or w, or use the edge from y to z instead of the edge from y to v or y to w, and drop the edge (v, w) if it appears.)

So, if x is a vertex in the connected component with v and w in H, then any vertex coming from x (either x itself if x ≠ v and x ≠ w or z otherwise) is in the same connected component as z.

Furthermore, if x is a vertex in another connected component from v and w in H, then there is no path from x to z. If there were, there must have been a path from x to either v or w but there was not.

Thus, the invariant is proven. If the algorithm reaches a point where there are no edges, the number of connected components is the number of points. Thus, if the algorithm terminates, it outputs the number of connected components of G.

(d) (3 points) Prove that this algorithm always terminates.

Solution:

Let F (G, H) be the number of edges in H. F is clearly always a nonnegative integer since graphs cannot have non-integer or negative numbers of edges. Furthermore, F is strictly decreasing.

When we make the transition from H to H′ we remove the edge (v, w), and we may remove other edges too (if there are edges from some node x to both v and w, these will be replaced with only one edge from x to z in H′.)

By the termination theorem, this algorithm terminates.

Problem 3 [9 points] Lines That Cross and Lines That Don’t

Suppose we have a set L of 26 different lines with equations in the form y = mx + b for real m and b. Prove that there is either

1. A set S of 6 lines that never intersect one another when x > 0, or

2. A set T of 6 lines such that any two of them intersect one another at some point where x > 0.

Hint: Use Dilworth’s Theorem.

Solution:

Let ⪯ be the relation on the set of 26 different lines such that mx + b ⪯ m′x + b′ if and only if at all points where x > 0, the height mx + b is less than or equal to the height m′x + b′. (This relation is equivalent to the relation that mx + b ⪯ m′x + b′ if and only if m ≤ m′ and b ≤ b′, but we won’t prove this here.)

This is a partial order. It is reflexive, since mx + b ≤ mx + b for every value of x. If mx + b ≤ m′x + b′ and m′x + b′ ≤ mx + b for all x > 0 then mx + b = m′x + b so the two lines must be the same (thus, the relation is antisymmetric). Finally, the relation is transitive since ≤ is transitive.

By Dilworth’s theorem, there is either a chain in this poset of size > 5 or there is an antichain of size ≥ (26/5).

If there is a chain of size 6 or greater, then the first six elements of it form the set S. If two lines are comparable they don’t intersect when x > 0. If they did, at say x = a, then one of them is higher at x = 2a but the other is higher at x = a/2. Thus, the chain forms the set S.

If there is an antichain of size 6 or greater, then the first six elements of it form the set T. If two lines are not comparable, there must be some point x = a > 0 such that ma+b < m′a+b but there must then be some point x = a′ > 0 such that ma′ + b > m′a′ + b′. Thus, the function (m′ − m)x + (b′ − b) has a value (a) that makes it greater than zero, and a value (a′) that makes it less than zero. Since this is a line, it must pass through zero at some point a′′ between a and a′. Since a and a′ are both greater than zero, a′′ must also be greater than zero, so the two lines intersect.

Problem 4 [10 points] Recurrence Relations

(a) (5 points) Find a closed form solution to the following homogenous recurrence relation,

A_{n} = −A_{n−1} + A_{n−2} + A_{n−3}

such that A_{0} = 1, A_{1} = 0, and A_{2} = 3.

Solution:

The characteristic equation for this recurrence is

r^{3} + r^{2} − r − 1 = 0

which factors to

(r + 1)(r^{2} − 1) = (r + 1)^{2}(r − 1) = 0.

So we get a closed form solution of the form

A_{n} = c_{1} + c_{2}(−1)^{n} + c_{3}n(−1)^{n}.

Using the initial conditions, we find that c_{1} + c_{2} = 1, so c_{2} = 1 − c_{1}. c_{1} − (1 − c_{1}) − c_{3} = 0, so c_{3} = 2c_{1} − 1, and

c_{1} + (1 − c_{1}) + 2(2c_{1} − 1) = 3
4c_{1} + 1 − 2 = 3
4c_{1} = 4

so c_{1} = 1, c_{2} = 0, and c_{3} = 1. Thus, the final answer is

A_{n} = 1 + n(−1)^{n}.

(b) (5 points) Find a closed form solution to the following inhomogenous recurrence relation:

A_{n} = −A_{n−1} + A_{n−2} + A_{n−3} + 4

where A_{0} = 1, A_{1} = 0, and A_{2} = 3.

Solution: We can use the general form for the homogenous part from part (a):

A_{n} = c_{1} + c_{2}(−1)^{n} + nc_{3}(−1)^{n}.

Now, let us guess a particular solution in the form an + b.

an + b = a(n − 3) + b + a(n − 2) + b − a(n − 1) − b + 4
an + b = an − 4a + b + 4
0 = −4a + 4
4a = 4

So a = 1 and b can be anything, so we will choose 0. Now, substituting the initial conditions, we get that c_{1} + c_{2} = 1 so c_{2} = 1 − c_{1}. c_{1} − c_{2} − c_{3} + 1 = 0, so c_{3} = 2c_{1}, and c_{1} + c_{2} + 2c_{3} + 2 = 3, so c_{1} + (1 − c_{1}) + 4c_{1} + 2 = 3 4c_{1} + 3 = 3, so c_{1} = 0. Thus, the solution is

A_{n} = (−1)^{n} + n

. Problem 5 [6 points] Summations

(a) (2 points) Find a simplified closed form for

∑_{i=0}^{∞} ∑_{j=1}^{n} \frac{1}{2^{i}}

Solution: The inner sum,

∑_{j=1}^{n} \frac{1}{2^{i}}

is very simple since j is not involved in the inner term. The closed form for this is simply

\frac{n}{2^{i}}

. Since n is a constant, we can take it out, and evaluate a simple infinite geometric sum to get ∑_{i=0}^{∞} ∑_{j=1}^{n} \frac{1}{2^{i}} = 2n

(b) (4 points) Find a simplified closed form for

∑_{i=0}^{n}(i + 1)x^{i}.

Solution: Consider that

\frac{d}{dx} (∑_{i=0}^{n+1} x^{i}) = ∑_{i=0}^{n}(i + 1)x^{i}.

However, the sum ∑_{i=0}^{n+1} x^{i} can be written in closed form as

\frac{x^{n+2} − 1}{x − 1}.

Taking the derivative of this yields

\frac{(n + 2)x^{n+1}}{x − 1} − \frac{x^{n+2} − 1}{(x − 1)^{2}} =

\frac{(n + 1)x^{n+2} − (n + 2)x^{n+1} + 1}{(x − 1)^{2}}.

Problem 6 [10 points] Combinatorics Let S be the set {a, b, c, d, e} and let T be the set {1, 2, 3, 4}. (2 points each)

(a) What is the number of binary relations from S to T?

Solution: The set of all binary relations is P(S × T). Since |S × T | = 20, the number of binary relations between S and T is 2^{20}.

(b) What is the number of functions from T to S?

Solution: To make a function from T to S, we must assign an element of S to each element of T. Thus, for each of the 4 elements in T we must make one of 5 choices. Therefore the number of functions from T to S is 5^{4}.

(c) What is the number of injective functions from T to S?

Solution: We must choose a permutation of 4 out of 5 elements. Thus, 5! is the number of injective functions. (We must make a choice of which of the 5 elements of S is mapped to from the first element of T, then a choice of which of the remaining 4 elements of S is mapped to from the second element of T, et cetera.

(d) What is the number of surjective functions from T to S?

Solution: 0. T is smaller than S so there cannot be a surjection from T to S.

(e) What is the number of surjective functions from S to T?

Solution: To form a surjective function, we first take an injective function from T to S (this takes care of the surjective requirement), and then choose which element of T is the image of the remaining element of S which hasn’t been paired up yet. There are 5! · 4 ways of doing this.

However, we have double-counted everything. For example, if the function is (1, 2, 3, 4, 1), we have counted this by choosing the injection (a, b, c, d) and then the element 1, AND by choosing the injection (e, b, c, d) and then the element 1. So, we must divide by 2 to take care of this; this leaves 2 · 5! as the final answer.

Problem 7 [16 points] Coloring Grid Graphs, Yet Again

Let G be a 4 by 4 grid graph:

Suppose we pick a random 4 color graph coloring of G, where the colors being used are red, green, blue, and yellow. That is, we pick uniformly at random from the set of all valid colorings. Let A be the event that vertex (1,1) is colored red, B be the event that vertex (1,2) is colored red, and C be the event that (1,1) and (2,2) are the same color. Let X be the number of “points” the graph coloring gives, where each red node is worth 1 point, each yellow node is worth 2 points, each blue node is worth 3 points, and each green node is worth 6 points.

(a) (2 points) What is Pr(A)?

Solution:

By symmetry, vertex (1,1) should be no more likely to be any one particular color than any other. Thus, the probability is 1/4.

(b) (2 points) What is Pr(B|\overline{A})?

Solution:

By symmetry, vertex (1,2) should be no more likely to be any one particular valid color (given that vertex (1,1) is colored red) than any other. Thus, the probability is 1/3.

(c) (2 points) What is Pr(A|C)?

Solution:

By symmetry, if vertices (1,1) and (2,2) are the same color, they should not be more likely to be any one color than any other. Thus, the probability is 1/4.

(d) (2 points) What is Pr(B|\overline{A} ∩ C)?

Solution:

By symmetry, if vertices (1,1) and (2,2) are both not red (which is what having \overline{A} and C both be true means), then vertex (1,2) should be no more likely to be any one valid color than any other. No matter which color vertices (1,1) and (2,2) are, red is one of three valid colors for vertex (1,2), so the probability is 1/3.

(e) (4 points) Which pairs of the events A, B, and C are independent?

Solution:

Obviously, since A and B cannot both be true at the same time, they are not independent.

However, P r(A|C) = P r(A) so A and C are independent.

P r(B|C) = 1/4 since if vertices (1,1) and (2,2) are the same color, they should be equally likely to be any particular color. With probability 3/4, they are not red, and then with probability 1/3, vertex (1,2) is red. With probability 1/4, (1,1) and (2,2) are red, and then with probability 0, vertex (1,2) is red. Thus, P r(B|C) = (3/4)(1/3)+(1/4)0 = 1/4 = P r(B). Thus, B and C are independent.

(f) (4 points) What is Ex(X)?

Solution: Let X_{v} be a random variable for vertex v, which determines the number of points that vertex contributes. Since X = ∑_{v∈G} X_{v}, by linearity of expectation, we have that

Ex(X) = ∑_{v∈G}Ex(X_{v}).

Since Ex(X_{v}) = (1)(1/4) + (2)(1/4) + (3)(1/4) + (6)(1/4) = 12(1/4) = 3, and there are sixteen vertices in G, this gives that

Ex(X) = 48.

Problem 8 [20 points] The Florida Election Suppose that in one Florida county populated exclusively with probability theory enthusiasts, there are 10,000 people. Every one of them votes independently of one another, and they vote for Bush with probability 2/5 and for Gore with probability 3/5.

(a) (2 points) Let X be a random variable that represents the number of votes Gore gets in this county. What is the expected value of X?

Solution: 6000.

(b) (3 points) What is the variance of X?

Solution: V (X) = 10000(2/5)(3/5) = 2400.

(c) (5 points) Using the Markov inequality, give an upper bound for the probability that Gore gets at least 2600 more votes than Bush.

Solution: If Gore gets at least 2600 more votes than Bush in the county, then X must be at least 6300 (since 6300 − 3700 = 2600). By Markov’s inequality,

P r(X ≥ 6300) ≤ \frac{6000}{6300} = \frac{20}{21}

(d) (5 points) Using the Chebyshev inequality, give an upper bound for the probability that Gore gets at least 2600 more votes than Bush.

Solution: Using the one-sided Chebyshev formula,

P r(X − Ex(X) ≥ t) ≤ \frac{V (X)}{V (X) + t^{2}}

with t = 300 gives an upper bound of \frac{2400}{92400} = \frac{2}{77}. However, the two-sided Chebyshev inequality is almost as good.

P r(X − Ex(X) ≥ t) ≤ P r(|X − Ex(X)| ≥ t) ≤ \frac{V (X)}{t^{2}},

with t = 300 gives an upper bound of \frac{2400}{90000} = \frac{2}{75}.

(e) (5 points) Using the Chernoff inequality, give a simplified upper bound for the probability that Gore gets at least 2600 more votes than Bush, or explain why the Chernoff bound does not apply.

Solution: Since the 6300 votes Gore would need for this to happen is equal to 21/20 times 6000, the expected number of votes Gore gets, the Chernoff inequality yields

P r(X ≥ (21/20)Ex(X)) ≤ e^{−αcEx(X)}.

Plugging in α = ln c + 1/c − 1 and evaluating gives that e^{−αcEx(X)} ≈ e^{−7.37} ≈ 0.000625.

Problem 9 [6 points] MIT Football MIT’s football coach goes to K-mart to buy 32 football jerseys. While he is away, instead of practicing, the team proves theorems about the numbers on the jerseys. For each of the theorems, fill in whichever blanks are asked for. You do not have to complete the proof. For example, Theorem 1 If the numbers on the jerseys are integers in the set {1, …, 31} then two of the jerseys have the same number. Pigeons: \underline{Jerseys} Pigeonholes: \underline{Integers in the set \{1, …, 31\}} Pigeon p is in hole h if: \underline{Jersey p has number h on it.}

(a) (2 points). Theorem 2 If the numbers on the jerseys are integers in the set {1, …, 100} then the difference between the numbers on some pair of jerseys is a multiple of 31. Pigeons: Jerseys Pigeonholes: Pigeon p is in hole h if:

Solution: Pigeonholes: Integers in the set {0, …, 30}. Pigeon p is in hole h if: The number on jersey p is equal to h modulo 31.

(b) (4 points). Theorem 3 If the numbers on the jerseys are integers in the set {1, …, 100} then if the jerseys are lined up in ascending order by their numbers, there is a nonempty consecutive subset of the jerseys whose numbers add up to a multiple of 32. Pigeons: Pigeonholes: Pigeon p is in hole h if:

Solution: Pigeons: Sums of the first i jerseys, from i = 1 to 32 Pigeonholes: Integers in the set {0, …, 31} Pigeon p is in hole h if: p ≡ h mod 32.

Problem 10 [6 points] Die Rolling Say you roll a fair 6-sided die. If you get a 6, you may roll again, and add 6 to the outcome; if you roll multiple 6’s in a row, you continue to roll again. So, for example, if you roll a 6 and then a 5, the outcome is 11; if you roll a 6, then a 6, then a 6, then a 2, the outcome is 20. What is the expected value of the outcome? Your answer should be in closed form.

Solution: Let R_{i} be the value of the ith die roll (if there is one). Let Q be the number of die rolls. Since Ex(R_{i}) does not depend on i, we can use Wald’s theorem to find the solution. Ex(R_{i}) = \frac{1}{6}(1 + 2 + 3 + 4 + 5 + 6) = \frac{21}{6} = \frac{7}{2}. Ex(Q) = ∑_{i=0}^{∞} \frac{1}{6^{i}} = \frac{1}{1−(1/6)} = \frac{6}{5}. So, Ex(∑_{i=1}^{Q} R_{i}) =Ex(R_{i})Ex(Q) = \frac{42}{10} = \frac{21}{5}. Another way of doing this problem would be to note that Ex(X) = \frac{1}{6}(1 + 2 + 3 + 4 + 5 + (6 + Ex(X))) = \frac{7}{2} + Ex(X)/6. Solving gives \frac{5Ex(X)}{6} = \frac{7}{2} so Ex(X) = \frac{42}{10} = \frac{21}{5}

Problem 11 [10 points] Chess Matches Math Moose and Theory Pig have been playing a series of chess games, and have noticed a number of facts:

• Math Moose plays white in any given game with probability 8/17.

• If Math Moose plays white, he is equally likely to win or lose.

• If Math Moose plays black, then with probability 8/9, he loses.

• If Math Moose wins, he always takes Theory Pig’s queen at some point in the game.

• If Math Moose plays white and loses, he takes Theory Pig’s queen with probability 1/2.

• If Math Moose plays black and loses, he takes Theory Pig’s queen with probability 1/4.

(a) (4 points) Define the sample space, and give the probability associated with each outcome.

Solution: The outcomes are that Math Moose...:

plays white, wins, and takes the queen: 4/17 plays white, loses, and takes the queen: 2/17 plays white, loses, and doesn’t take the queen: 2/17 plays black, wins, and takes the queen: 1/17 plays black, loses, and takes the queen: 2/17 plays black, loses, and doesn’t take the queen: 6/17 plays white, wins, and doesn’t take the queen: 0 plays black, wins, and doesn’t take the queen: 0

(b) (3 points) What is the probability that Math Moose plays white, given that he wins?

Solution: The probability is \frac{4/17}{5/17} = \frac{4}{5}.

(c) (3 points) What is the probability that Math Moose wins, given that he takes Theory Pig’s queen?

Solution: The probability is \frac{5/17}{9/17} = \frac{5}{9}.

Problem 12 [8 points] Overloading Circuits

A memory card produced by NP Computer Hardware, Inc., consists of infinitely many memory cells in series. The card is attached to a computer at one end. If there is a power surge, the first memory cell burns out. Furthermore, if a memory cell burns out, the next memory cell after that one burns out with probability p. Otherwise, memory cells have no chance of burning out in a power surge.

(a) (5 points) Express the expected number of memory cells that burn out in a power surge, in terms of p. (Hint: use linearity of expectation.)

Solution:

Let X_{i} be an indicator variable which is 1 if during a power surge, memory cell i burns out, and is a 0 otherwise.

We are asked to find Ex(∑_{i=0}^{∞} X_{i}) = ∑_{i=0}^{∞} Ex(X_{i}).

The probability that X_{i} is 1 is equal to p times the probability that X_{i−1} is 1. This gives the simple recurrence relation X_{n} = pX_{n−1} with initial condition X_{0} = 1, which simplifies to X_{n} = p^{n}. Thus, the value we want is ∑_{i=0}^{∞} p^{n} = \frac{1}{1−p}, provided that p < 1. If p = 1 all the memory cells burn out.

(b) (3 points) It is discovered that the mean number of memory cells that burn out from a power surge is 10. What is p?

Solution:

If 10 = \frac{1}{1−p} then 10 − 10p = 1 so 10p = 9 so p = 9/10.