[induction2]

Problem 1 [12 points] Source: s99 ps3

Topics: Induction, Graphs, Recursive Definitions

This problem concerns Hamiltonian circuits in n-cubes. A Hamiltonian circuit in a graph is a circuit 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 cube is two squares with corresponding corners joined.

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

Solution

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

Solution The dotted edges in the diagram above form a Hamiltonian circuit.

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

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

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

Problem 2 [10 points] Source: s97 ps3

Topics: Fibonnacci Numbers, Strong Induction

Show that the Fibonnacci number f_{n} satisfy f_{n} ≤ 2^{n} using strong induction by filling in the blanks below in the proof reasoning.

E.g.:

Let P (n) = F_{n} ≤ 2^{n} Prove: ∀n ≥ 0(P (n))

1. (Base) P (0) F_{0} = 0 ≤ 2^{0}

2. (Base) P (1) F_{1} = 1 ≤ 2^{1}

3. (Inductive step) ∀n ≥ 1[(∀i, 0 ≤ i ≤ n(P (i))) ⇒ P (n + 1)] 1. Fix n ≥ 1

2. (∀i, 0 ≤ i ≤ n(P (i))) ⇒ P (n + 1)

1. Assume ∀i, 0 ≤ i ≤ n(P (i))
2. P (n + 1)

1. F_{n} ≤ 2^{n} Inductive hypothesis 3.2.1

2. F_{n−1} ≤ 2^{n−1} Inductive hypothesis 3.2.1

3. F_{n+1} = F_{n} + F_{n−1} Definition of Fibonacci numbers

4. F_{n+1} ≤ 2^{n} + 2^{n−1} Plug the inequalities into the equation

5. F_{n+1} ≤ 2^{n+1}

1. 2^{n−1} ≤ 2^{n} Algebra

2. 2^{n} + 2^{n−1} ≤ 2^{n+1} Algebra

3. QED Algebra (3.3.4 and 3.3.5.2)

6. QED Definition of P (n + 1)

3. QED Implication 3. QED UG

4. QED Strong induction

]]] Problem 3 [12 points] Source: s97 ps3

Topics: False Proofs, Well Ordering, Induction

Find the flaws in the following “proofs.”

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

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

(c) [4 points] CLAIM: every number can be described in a phrase of less than eighty characters.

PROOF: Well-ordering. Let S be the set of numbers that cannot be described in a phrase of less than eighty characters. If it is nonempty, it contains a smallest element. This is “The smallest number that cannot be described in less than eighty chracters.” This is a description of that number in less than eighty characters, a contradiction. Since the assumption that S was nonempty yields a contradiction, S must be empty and the claim is proved.

Solution The flaw in the above proof is that the set of numbers that can be described in less than eighty characters, is not a well-defined set.

[wellordering1]

Problem 4 [12 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). Prove that every pair of natural numbers has a least common multiple. Using unique factorization, show that a · b = gcd(a, b) · lcm(a, b).

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.

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 5 [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, with exactly one table and a single associated chair at each point. 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 must occur 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.

[summations1]

Problem 6 [16 points] Source: Kyle’s brain, modified from PS6 n4

Topics: Summations, asymptotics

Prove that the “average” number of perfect square^{1} divisors of a number of size n is bounded from above by a constant. More formally, let t(n) be the number of divisors of the number n that are themselves perfect squares, and let

T (n) = \frac{1}{n} ∑_{j=1}^{n} t(j)

be the average number of perfect square divisors of all numbers less than or equal to n. Show that there exists a constant c such that for all n, T (n) ≤ c.

Hint: Let the function f(i, j) = 1 if i^{2} is a divisor of j, and 0 otherwise. What do the row and column sums of f(i, j) mean?

Solution Consider the image of the function f(i, j) as a matrix whose rows and columns correspond to values of i and j respectively; that is, element (i, j) of the matrix denotes whether or not i^{2} divides j.

j
f(i, j) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
i 2 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 ⋯
3  0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
⋮  ⋮

Notice that the sum of each column j corresponds to the number of perfect square divisors of the number j and the sum of each row i corresponds to the number of multiples of the number i^{2}. As a result, the number of multiples of i^{2} between 1 and n can be compactly represented as ⌊n/i^{2}⌋.

It follows that

T (n) = \frac{1}{n} ∑_{j=1}^{n} t(j)

= \frac{1}{n} ∑_{i=1}^{⌊\sqrt{n}⌋} ∑_{j=1}^{n} f(i, j)

= \frac{1}{n} ∑_{i=1}^{⌊\sqrt{n}⌋} ⌊\frac{n}{i^{2}} ⌋

1x is a perfect square if there is some natural number y such that y^{2} = x.

T (n) can then be bounded from above as follows:

T (n) ≤ \frac{1}{n} ∑_{i=1}^{⌊\sqrt{n}⌋} \frac{n}{i^{2}}

= ∑_{i=1}^{⌊\sqrt{n}⌋} \frac{1}{i^{2}}

≤ 1 + ∫_{1}^{√\overline{n}} \frac{1}{x^{2}} dx
= 1 + \frac{\sqrt{n} − 1}{\sqrt{n}} ≤ 2

[recurrences2] Problem 7 [12 points] Source: Kyle Topics: Recurrences

(a) [6 points] Iterate the following recurrence to find a pattern:

T (n) = a_{0}T (n/b_{0}) + a_{1}T (n/b_{1}) + f(n)

where T (n/(b_{0}^{i}b_{1}^{m−i})) = c for all i ∈ {1, …, m} with a_{{0,1}}, b_{{0,1}}, and c all constant. Demonstrate a non-recurrent formula that may have summations in it. Solution Denote g(x) = T (n/x), so g(b_{0}^{i}b_{1}^{m−i}) = c. Then:

T (n) = a_{0}g(b_{0}) + a_{1}g(b_{1}) + f(n)
= a_{0}^{2}g(b_{0}^{2}) + 2a_{0}a_{1}g(b_{0}b_{1}) + a_{1}^{2}g(b_{1}^{2})

+f(n) + [a_{0}f(n/b_{0}) + a_{1}f(n/b_{1})]

= a_{0}^{3}g(b_{0}^{3}) + 3a_{0}^{2}a_{1}g(b_{0}^{2}b_{1}) + 3a_{0}a_{1}^{2}g(b_{0}b_{1}^{2}) + a_{1}^{3}g(b_{1}^{3})

+f(n) + [a_{0}f(n/b_{0}) + a_{1}f(n/b_{1})] + [a_{0}^{2}f(n/a_{0}^{2}) + 2a_{0}a_{1}f(n/(b_{0}b_{1})) + a_{1}^{2}f(n/a_{1}^{2})] ⋮

= ∑_{i=0}^{m} (\binom{m}{i}a_{0}^{i}a_{1}^{m−i}g(b_{0}^{i}b_{1}^{m−i}))

+ ∑_{j=0}^{m} ∑_{i=0}^{j} (\binom{j}{i}a_{0}^{i}a_{1}^{j−i}f(n/(b_{0}^{i}b_{1}^{j−i})))

= c(a_{0} + a_{1})^{m}

+ ∑_{j=0}^{m} ∑_{i=0}^{j} (\binom{j}{i}a_{0}^{i}a_{1}^{j−i}f(n/(b_{0}^{i}b_{1}^{j−i})))

(b) [6 points] Find asymptotically tight bounds for the following recurrence:

T (n) = 8T (n/2) + n^{3} (log n)^{2}

given that T (1) = 1. You may assume n is a power of 2. Note that the master theorem does not apply to this recurrence.

Solution Use the first part, with a_{0} = 4, a_{1} = 4, b_{0} = b_{1} = 2, m = log n, c = 1, and f(n) = n^{3} log^{2} n. (Note that we can’t take a_{0} = 0 or a_{1} = 0, since 0^{0} is indeterminate; we could, however, have used any other a_{0} and a_{1} such that a_{0} + a_{1} = 8.)

Plugging and chugging:

T (n) = 4T (n/2) + 4T (n/2) + n^{3} log^{2} n
= 1(4 + 4)^{log n} + ∑_{j=0}^{log n} ∑_{i=0}^{j} (\binom{j}{i}4^{j}(n/2^{j})^{3} log^{2}(n/2^{j}))

= n^{3} + ∑_{j=0}^{log n} (8^{j}(n/2^{j})^{3} log^{2}(n/2^{j}))

= n^{3} + n^{3} ∑_{j=0}^{log n} (log^{2}(n/2^{j}))

= n^{3} + n^{3} ∑_{j=0}^{log n} (log^{2} n − 2j log n + j^{2})

= n^{3} + n^{3} (log^{3} n + log^{2} n) − 2n^{3} log n ∑_{j=0}^{log n} j + n^{3} ∑_{j=0}^{log n} j^{2}

= n^{3} + n^{3} (log^{3} n + log^{2} n) − n^{3} (log^{3} n + log^{2} n) + n^{3} ∑_{j=0}^{log n} j^{2}

= n^{3} + n^{3} ∑_{j=0}^{log n} j^{2}

We must bound the last part, ∑_{x=0}^{log n} x^{2}, by the integral method:

∑_{x=0}^{Y} x^{2} ≤ ∫_{0}^{Y} (x + 1)^{2}dx

= \frac{1}{3}(x + 1)^{3}|_{0}^{Y}
= \frac{1}{3}(Y + 1)^{3} − \frac{1}{3}

and

∑_{x=0}^{Y} x^{2} ≥ ∫_{0}^{Y} x^{2}dx

= \frac{1}{3}x^{3}|_{0}^{Y}
= \frac{1}{3}Y^{3}

so the last term is asymptotally bounded by n^{3} log^{3} n; thus, the entire summation is Θ(n^{3} log^{3} n).

[recurrences3]

Problem 8 [14 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) that represents the number of new complaints on day n.

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

(b) [6 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.

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) [6 points] Scully does some more digging and notices that 6n new 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.

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.

[relations7] Problem 9 [12 points] Source: kdmc Topics: Relations Let the relations R and S be binary relations on the set ℕ of natural numbers. Define R as follows: ∀(a, b) ∈ ℕ×ℕ(a, b) ∈ R ⟺ a mod 4 = b mod 4. Define S as follows: ∀(a, b) ∈ ℕ×ℕ(a, b) ∈ R ⟺ 2^{a} = b.

(a) [3 points] Prove that R is transitive.

(b) [3 points] Prove that R is symmetric.

(c) [3 points] Find R ∩ S.

(d) [3 points] Let T = S ∘ R. ??? what is the rest of the question?

[statemachines1]

Problem 10 [15 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}. Initially, the state is that of the “linear graph” (1 ⟶ 2 ⟶ 3 ⟶ 4 ⟶ 5). The transitions allowed by the state machine are the following:

• remove(a,b):

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

Effect is to remove the edge.

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

• add-in(a,b):

Can occur if a has no outgoing edges. Effect is to add the edge b⟶ a.

• reverse(a):

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.

• trans(a,b,c) (a,b,c distinct): Can occur if there is an edge from a to b. Effect is to remove the edge.

State whether each of the following digraphs is 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.

(a) [3 points] The graph that is the same as the line graph above, but with the additional edge 5⟶ 1.

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

(b) [6 points] The line graph in the opposite direction (1 ⟵ 2 ⟵ 3 ⟵ 4 ⟵ 5).

Solution Reachable: reverse(1), reverse(2), reverse(1), reverse(3), reverse(2), reverse(1), reverse(4), reverse(3), reverse(2), reverse(1).

(c) [6 points] Now suppose we have the same state machine, but without the remove and reverse transitions. 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 any 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.

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.

[combinatorics1]

Problem 11 [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.

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.

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.

[combinatorics4] Problem 12 [14 points] Source: Kyle’s brain Topics: Combinatorics, basic probability, product rule Theorem. Let 0 ≤ p_{i} ≤ 1 for all i ∈ {1, …, n}. Then,

∑_{S⊆{1,... ,n}} ((∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j}))) = 1

Note that ∑_{S⊆T} means to sum over all possible subsets S of T.

(a) [6 points] Give a combinatorial proof of the theorem. Hint: Consider choosing an element from {a_{1}, b_{1}} × {a_{2}, b_{2}} × {a_{3}, b_{3}} × ⋯ × {a_{n}, b_{n}} where we have a probability p_{i} of choosing a_{i} for the i^{th} element of the tuple. Solution Use the hint given. For a given subset S of the indices {1, …, n}, the summand is the probability of choosing a_{i} for the indices in S and b_{i} for the indices not in S. Since this covers exactly the possible ways of choosing a tuple given these probabilities, the total probability must be 1.

(b) [8 points] Give an algebraic proof of the theorem. Hint: Use induction. Solution Base case: When n = 1, we have

p_{i} + (1 − p_{i}) = 1

Inductive case: Assume the theorem for all n ≤ N. Now we must prove it for N + 1.

∑_{S⊆{1,... ,N+1}} ((∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j}))) = ∑_{S⊆{1,... ,N}} ((p_{N+1} ∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j})))

+ ∑_{S⊆{1,... ,N}} ((∏_{j∈S} p_{j}) ((1 − p_{N+1}) ∏_{j∉S}(1 − p_{j})))

= p_{N+1} ∑_{S⊆{1,... ,N}} ((∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j})))

+(1 − p_{N+1}) ∑_{S⊆{1,... ,N}} ((∏_{j∈S} p_{j}) (∏_{j∉S}(1 − p_{j})))

= p_{N+1} · 1 + (1 − p_{N+1}) · 1
= 1

[expectation1] Problem 13 [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? Solution 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. Solution \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?

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

Solution 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?

[expectation2] Problem 14 [10 points] Source: Nancy Topics: Expectation 100 students enter a cafeteria with very large tables, one at a time. As each students enters, he or she looks around to see if any of his friends are already there. If so, he/she joins one of his friends’ tables. If not, he/she starts a new table. Assume that, for each pair of students, the probability that they are friends is p. Moreover, all these pair probabilities are independent.

(a) [5 points] For the i^{th} person to enter the cafeteria, what is the probability he/she starts a new table? Solution (1 − p)^{i−1}

(b) [5 points] What is the expected number of occupied tables after everyone has entered? Solution Add this from i = 1 to n.

[expectation3] Problem 15 [15 points] Source: David R’s Brain Topics: Expectation, product rule There is a casino in St. Petersburg where you have the choice of betting any portion of your wealth on either of two games: in the first game, you either receive 3 times what you bet or lose it all with equal probability. In the second game the casino gives you 1.4 times what you bet with probability 1 (this casino is understandably very popular). Each trial of the two games are played simultaneously.

(a) [3 points] Call S_{1} and S_{2} the fraction of your wealth you bet on the two games (notice S_{1} + S_{2} ≤ 1). What values of S_{1} and S_{2} maximize the expected value of your wealth after 1 trial? What is the maximum expected value of your wealth? Solution S_{1} = 1, max is 1.5

(b) [3 points] What strategy maximizes your expected wealth after n trials? Solution Always have S_{1} = 1

(c) [3 points] Using that strategy, what is the probability that after 10 trials, you have more money than you started with? Solution 1 − 2^{−10} (d) [3 points] After 2n trials, what is the most likely number of trials in game one that are wins. And what is the probability that this occurs?

Solution n, f_{2n,0.5}(n) ≈

(e) [3 points] What fraction of your wealth should you bet on each trial of the two games, if you want to maximize your wealth after 2n trials in the most likely case that you found above? (i.e. suppose that there are that number of wins over the course of the 2n trials). Assume that it is in your interest to have S_{1} + S_{2} = 1.

Solution Maximize (1.4 + 1.6S_{1})^{0.5}(1.4 − 1.4S_{1})^{0.5} over S_{1}. S_{1} = 0.0625.

[wald1]

Problem 16 [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 iid random variables X_{i} and a stopping rule 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] Use Wald’s Identity to find Ex[T]

Solution 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 Identity

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

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

(a) [4 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) [4 points] Give an example distribution of weights showing that your bound in the first part is tight. Solution 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) [4 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. Solution Use one-sided Chebyshev

(d) [4 points] Give an example distribution of weights showing that your bound in the previous part is tight. Solution LTTR [pmethod1] Problem 18 [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? 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] Now, upper bound the probability that some player wins no more than one game. Solution 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. Solution This is just the complement of the previous part, so 1 − \frac{n^{2}}{2^{n−1}} .

(d) [2 points] Show a condition implying 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 occuring, then there must be a configuration in which that event occurs.

[indep1] Problem 19 [10 points] Source: Kyle Topics: Mutual independence Consider three random variables, A, B, C, each of which takes on either −1 or 1 with uniform probability, and a fourth random variable D = ABC.

(a) [6 points] Show that any three of these variables are mutually independent, but all four are not.

(b) [3 points] Explain briefly why this is the case. Solution Enumerate the possibilities; it turns out that, for any three (x, y, and z from {A, B, C, D}), Pr(x = 1 ∩ y = 1 ∩ z = 1) = Pr(x = 1) Pr(y = 1) Pr(z = 1), and Pr(x = 1 ∩ y = 1) = Pr(x = 1) Pr(y = 1) and so on. However, four variables overdetermine the possibilities: either the probability of the intersection is exactly 1 (if the relation is satisfied), or is 0 (otherwise).

(c) [6 points] Extend this theorem to n random variables X_{1}, …, X_{n} and their product Y = ∏_{i=1}^{n} X_{i}, and argue its correctness. Solution TBD [intransitivity1] Problem 20 [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) Calculate Pr(B beats A), Pr(C beats B), Pr(D beats C), and Pr(A beats D). Solution

• 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 is not reflexive. (For instance, < on the natural numbers is a strict partial order, while ≤ on the same set is a partial order.)

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

[prob1] Problem 21 Source: Nancy Topics: Conditional probability, independence, product rule, inclusion-exclusion, set theory and probability Suppose A, B, and C are events in a probability space, where A and C are independent events, B and C are independent events, and B ⊆ A. Suppose also that Pr(A) = 1/100, Pr(B) = 1/10, 000, and Pr(C) = 1/1000. Calculate each of the following. If it is impossible to determine the value exactly from the given information, then give the range of possible values.

(a) [1 points] Pr(A ∩ C) Solution 1/10^{5}

(b) [1 points] Pr(B ∩ C) Solution 1/10^{7}

(c) [1 points] Pr(A ∩ B) Solution 1/10^{4}

(d) [2 points] Pr(B|A) Solution 1/100

(e) [2 points] Pr(B|C) Solution 1/10^{4}

(f) [2 points] Pr(B − C) Solution 1/10^{4} − 1/10^{7}, or .0000999, approximately .0001

(g) [2 points] Pr(B ∪ C)

Solution 1/10^{4} + 1/10^{3} − 1/10^{7}, or .0010999, approximately .0011 (h) [2 points] Pr(A ∩ (B ∪ C)) Solution 1/10^{4} + 1/10^{5} − 1/10^{7}, or .0001099, approximately .00011 (i) [2 points] Pr(B|A ∩ (B ∪ C)) Solution .0001/.0001099, slightly less than 1 [diagnosis1] Problem 22 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) If the test is given to a random person in the population, then what is the probability that it comes out positive? Solution

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

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

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

Approx. .004

(c) If a person gets a negative test result, then what is the probability that he has C.R.? 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. .0025