Massachusetts Institute of Technology Handout 53 6.042J/18.062J: Mathematics for Computer Science December 12, 2000 Professors Nancy Lynch and Srinivas Devadas

Practice Final

Your Name:

Circle the name of your Tutorial Instructor:

Andrej  Wes  Dwaine  Andrew
Moses  Zulfikar  George  Nitin

Write the hour at which your Friday tutorial began

• This quiz is open book/notes.

• This quiz is 18 pages long; please check that you have all pages.

• Put your name on the top of every page — these pages may be separated for grading.

• Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Please keep your entire answer to a problem on that problem’s page.

• You may assume any of the results presented in class or in the lecture notes, but you must explicitly cite which results you are using and how you are using them.

• Show your work, as partial credit will be given. You will be graded not only on the correctness of your answer, but also on the clarity with which you express it.

• Be neat and write legibly.

• GOOD LUCK!

DO NOT WRITE BELOW THIS LINE

Problem Points  Grade  Grader
1  12
2  8
3  10
4  10
5  12
6  12
7  10
8  12
9  10
10  12
11  14
12  12
13  10
14  12
Total  156

Handout 53: Practice Final  1  Name:

Problem 1 [12 points] 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] Problem 2 [8 points] 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.

(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}.

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

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

Problem 4 [10 points] 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.

Problem 5 [12 points] 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.

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

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

Handout 53: Practice Final  7  Name:

Problem 6 [12 points] 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.

Handout 53: Practice Final  8  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.

Problem 7 [10 points] Prove combinatorially that the number of even-sized subsets of a set S ≠ ∅ is equal to the number of odd-sized 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.

Problem 8 [12 points] 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?

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

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?

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

Problem 9 [10 points] 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}

(b) [5 points] Use Wald’s Theorem to find Ex[T] Problem 10 [12 points] 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.

(b) [3 points] Give an example distribution of weights showing that your bound in the first part is tight.

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.

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

Problem 11 [14 points] 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?

(b) [3 points] Now, upper bound the probability that some player wins no more than one game.

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

Handout 53: Practice Final  15  Name:

(d) [2 points] Show a condition implying a positive probability of all players winning at least two games.

(e) [4 points] Explain briefly why your condition implies the existence of such a tournament.

Problem 12 [12 points] 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.

Problem 13 [10 points] 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).

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.

Problem 14 [12 points] 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?

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

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