Description
Problem 1 (15+1 points)
Let n be an even positive integer, and let us construct a “bullseye” sequence of n squares(S1, . . . , Sn)
as follows: S1 is a square with side length 1, and the interior of S1 is red. Now for every i ≥ 2, the
square Si has side length i, and Si−1 is entirely contained in Si
. Every square is centered about the
same point, and their orientations are identical.
The regions Si \ Si−1 alternate in color between blue and red. Thus, the border surrounding S1
(i.e., the region S2 \ S1) is blue, the border surrounding S2 (i.e., S3 \ S2) is red, and so on. Since n
is even, the outermost border is always blue. See Fig. 1 for the picture when n = 4.
Figure 1: The figure corresponding to Problem 1 when n = 4.
Let R denote the total area of the regions colored red, and let B denote the total area of regions
colored blue. Give a closed form expression (i.e., no summations) for B/(R + B), and prove your
result.
Problem 2 (15+1 points)
Consider a sequence of real numbers (a1, a2, . . .) defined as follows:
– The first two terms are a1 = 1 and a2 = 0.1.
– If n ≥ 3, then an = 0.01 · an−2 + 0.1 · an−1.
Let S denote the sum of all of the terms of the sequence, that is, S =
P∞
i=1 ai
.
(a) (10 points) Prove that S ≤ 2. (Hint: How does the value of an compare to 2
−n?)
(b) (5 points) State the exact value of S. (Justification is not required, but encouraged.)
Problem 3 (10+1 points)
Suppose there are n ≥ 3 people who each simultaneously flip a coin that returns H with probability
p and T with probability 1 − p. Compute the probability that there exists a person whose result is
unique among all results, and justify your result.
Problem 4 (15+1 points)
Suppose we flip a fair coin n times, where n is an even positive integer. For every positive integer `,
an `-streak is a consecutive sequence of ` flips that all return the same result. What is the probability
of obtaining an (n/2)-streak? Justify your result.
Problem 5 (20+1 points)
Suppose a car engine manufacturer creates a faulty engine with probability 0.005. Furthermore,
a faulty engine emits an odor with probability 0.95, while a non-faulty engine emits an odor with
probability 0.1. Now let X be a fixed engine, and compute the following values. Every response
should be justified.
(a) (5 points) What is the probability that X emits an odor?
(b) (5 points) Given that X emits an odor, what is the probability that X is faulty?
(c) (5 points) Given that X does not emit an odor, what is the probability that X is not faulty?
(d) (5 points) Suppose a novice mechanic assumes that an engine is faulty if and only if it emits an
odor, and the mechanic examines X for an odor. What is the probability that the mechanic’s
conclusion is incorrect?
Problem 6 (25+2 points)
In this problem, we will study the notion of spanning trees in multigraphs. A multigraph is a graph
in which multiple edges between two vertices is permitted. More formally, a multiset is a set in
which repetition of elements is allowed (e.g., {1, 3, 1, 2}). A multigraph is a pair (V, E) where V
is a non-empty finite set and E is a multiset containing subsets of V of size 2.
Now let G = (V, E) be a multigraph, and let e = {u, v} be an edge of G. We can contract the
edge e to create a graph, denoted G \ e, as follows: the vertex set of G \ e is equal to V \ {v}. We
construct the edge set of G \ e as follows:
1. Add all of the edges of G that do not contain v as an endpoint.
2. For every edge {v, x} of G, add the edge {u, x}.
In other words, the vertices u and v become a single vertex that is adjacent to all vertices that were
adjacent to u or v (or both). Furthermore, we let G−e denote the graph G with e removed from the
edge set. Now let τ (G) denote the number of spanning trees in G.
(a) (15+1 points) Prove the following: τ (G) = τ (G − e) + τ (G \ e).
(b) (10+1 points) Let e1 and e2 be two distinct edges of G, and let T be a spanning tree of G
chosen uniformly at random (from the set of all spanning trees of G). What is the probability
that T contains e1 or e2, but not both? Write your answer in terms of the τ function, and
prove your result.