CS 70 Discrete Mathematics and Probability Theory
Fall 2020 Rao Final Solutions
PRINT Your Name: Oski Bear
SIGN Your Name: OS K I
Do not turn this page until your instructor tells you to do so.
CS 70, Fall 2020, Final Solutions 1
SID:
1. Pledge.
Berkeley Honor Code: As a member of the UC Berkeley community, I act with honesty, integrity, and
respect for others.
In particular, I acknowlege that:
• I alone am taking this exam. Other than with the instructor and GSI, I will not have any verbal, written,
or electronic communication about the exam with anyone else while I am taking the exam or while
others are taking the exam.
• I will not have any other browsers open while taking the exam.
• I will not refer to any books, notes, or online sources of information while taking the exam, other than
what the instructor has allowed.
• I will not take screenshots, photos, or otherwise make copies of exam questions to share with others.
Signed:
2. Long Ago. Pts: 2/2/2/2/3/3/3
1. A∨¬(B∧C)≡ A∨ (¬B∨¬C)
Answer: True. A∨¬(B∧C)≡ A∨ (¬B∨¬C)
2. ¬∀x,∃y,Q(x,y)≡ ∃x,∃y,¬Q(x,y)
Answer: False. ¬∀x,∃y,Q(x,y)≡ ∃x,∀y,¬Q(x,y)
3. P =⇒ Q is logically equivalent to ¬Q∨P.
Answer: False. Its ¬P∨Q.
4. Consider a stable matching instance where S is the job optimal stable pairing. Consider a run of the
job-propose matching algorithm, where one candidate c rejects a job j that they should not have in one
step. That is, c recieves an offer from j and j′ and chooses j′ instead of j, when j was ahead of j′ in
their preference list.
Let P be the resulting pairing.
(a) For every instance, job j cannot do better in P than in S. (Better means get a partner who they
prefer more.)
Answer: True. If ( j,c) ∈ S, of course j does worse since they propose in order. It ( j,c) 6∈ S,
consider that ( j′,c) ∈ S and ( j′,c) ∈ P then the pairings are the same overall. We have ( j′,c) 6∈ S
and ( j′,c) ∈ P, but then the candidate prefers j to j′ and also no others are preferred more, so
( j,c) ∈ S. This is a contradiction.
(b) Every candidate other than c does as well or better in P than in S.
Answer: False. The job that c takes over j and perhaps ends up with may be first in another
candidate’s list and have been paired with that candidate in S.
(c) Every job other than j does as well or better in P than in S.
Answer: False. Consider that ( j,c),( j′′,c′′) ∈ S, and c′′ is first on j′′’s list. Moreover, wehn j is
rejected by c proposes to c′′ who prefers j to j′′. Now j′′ is out of luck.
3. Graphs: Pts: 3/3/3/2
1. Consider a graph on n vertices with exactly one cycle and m edges. What is the number of connected
components? (Hint: m≤ n.)
2
SID:
Answer: n−m+1. Remove an edge on the cycle and add n−1− (m−1) = n−m edges to connect
components and get a tree. Each addition reduced the number of components by 1. Thus the number
of components is n−m+1.
2. For a tree on n vertices, what is the expected number of connected components if each edge is deleted
with probability 1/3?
Answer: 1+(n−1)/3. E[deleted edges] = (n−1)/3. The number of components is 1 + the number
of deleted edges.
3. If we delete every edge with probability 1/2 from an Eulerian graph on n vertices, what is the expected
number of odd degree vertices in the remaining graph?
Answer: n/2. Each vertex is equally likely to be of odd or even degree as at least one edge.
4. Every simple cycle is 2-colorable.
Answer: False. An odd cycle is not 2 colorable.
4. Mostly Modular.Pts: 2/2/2/2/3/3/3/3/3/3/3
1. ∀ nonzero x,y ∈ N gcd(x,y mod x) = gcd(x,y).
Answer: True. x = id,y = jd iff and only if x = id and y− k jd = md for integers k,m.
2. ∀ nonzero x,y ∈ N, gcd(x,x mod y) = gcd(x,y).
Answer: False. Let x = 8,y = 3.
3. Give an example of positive integers for a and n where
(1 ·2 · · ·(n−1))an−1 6= (1 ·2 · · ·(n−1)) (mod n).
a: n:
Answer: a = 2,n = 4. One can check but the key is that a and n are not relatively prime.
4. Let S = {x : x ∈ {1, . . . ,34} and gcd(x,35) = 1}?
(a) What is the size of the set S?
Answer: 24. (7−1)(5−1) from RSA. Removing multiples of 7 and 5 from the range {0, . . . ,34}.
(b) What is a|S|+1 (mod 35) for a ∈ S?
Answer: a. a|S|+1−a = 0 (mod 35) from the proof for RSA.
(c) What is a|S|+1 (mod 35) for a 6∈ S?
Answer: a. a|S|+1−a = 0 (mod 35) from the proof for RSA.
5. What is 18−1 (mod 13)?
Answer: 8. 18 = 5 (mod 13). 8×5 = 40 = 1 (mod 13)
6. If x = 1 (mod 13) and x = 0 (mod 18) then what is x (mod 234)? (Note: 234 = 18×13)
Answer: 144. Using chinese remainder theorem except on need one term. 1×8×18 (mod 234).
7. For primes, p and q, where e = d−1 (mod (p−1)(q−1))?
(a) What is aed (mod q)? (Answer cannot use e or d, but may use numbers, a,p or q.)
Answer: a. This is the RSA scheme.
(b) Find an x≤ pq, where p|(aed− x). (Answer is an expression that may use a, p, and q.)
Answer: a. This is the RSA scheme.
5. Polynomials.Pts: 3/3/3
3
SID:
1. Given a polynomial, x3 +a2x2 +a1x+a0 modulo 7 with roots at 3, 1, and 6. What is a0? (Notice that
the coefficient of x3 is 1.)
Answer: 3 (mod 7). The polynomial is (x−3)(x−1)(x−6) so a0 =−3×1×6 (mod 7).
2. Working (mod 5), find a polynomial modulo 5 of degree 2 that has roots at 0 and 3, and goes through
point (2,3)
Answer: (x− 0)(x− 3). Consider ∆2(x) =
(x−0)(x−3)
−2 = 2(x− 0)(x− 3), multiply it by 3 as the other
values are zero.
3. Consider that one encodes a message of n numbers (mod m), by forming a degree n−1 polynomial
using the numbers as coefficients, and sending 2n− 1 points. If each point is erased with probability
1/2, what is the probability that the original message can be reconstructed? (Hint: each pattern of
erasures is equally probable.)
Answer: 1/2. If majority are delivered, this workds. For each configuration of with k erasures there is
a configuration with 2n−1−k erasaures. In one case, the majority are delivered. Thus, the probability
that the majority is delivered is 1/2.
6. Countability/Computability Pts: 2/2/2/2/2/2
1. For every pair of distinct rational numbers there is a rational number in between them.
Answer: True. If x,y are rational than so is x+ y/2.
2. The rational numbers are uncountable.
Answer: False. One can enumerate the positive ones by enumerating pairs (a,b) of natural numbers
in order of the sum of the numerators. Then any rational a/b is represented at least once in this list.
To get all natural numbers alternate between positive and negative numbers to form a list.
3. There is a program that takes a program P, an input x, and a number n and determines whether P run
on input x ever writes to memory location n.
Answer: False. Assume there is such a program WRITES. Given an instance P and x of the halting
problem we modifying P to write into one memory location higher. Then, we can modify it to write
to location 0 if it exits. Let P′ be the resulting program. Then we can call WRITES on P′, x and 0.
WRITES will answer affirmatively if and only if P halts on x.
4. There is a program that takes a program P, an input x, and a number n and determines whether P run
on input x ever writes to any memory location i≥ n.
Answer: True. One can simulate the program and check if it ever writes to a memory location larger
than n. If it runs forever and never writes to a memory location larger than n, then a configuration of
the first n memory location and the program counter must repeat. This can be kept track of as well.
5. A program “knows” a real number if it takes an integer n and outputs the nth bit of the real number.
(Note: positive values of n signify to the left of the decimal point, and negative ones to the right.)
(a) There is a program that knows π .
Answer: True. There are a number of ways to calculate pi: e.g., approximate a circle with a
polygon and compute the perimeter.
(b) For every real number x, there is a program that knows x.
Answer: False. There are more real numbers(uncountable) than there are programs (countable).
7. A little counting.Pts: 3/3/3/3
4
SID:
1. What is the number of ways to have k strictly positive numbers that add up to n?
Answer:
(n−1
k−1
)
. Have n− k stars and k−1 bars. The ith number correspond to 1+ the number of stars
before the ith bar, and the kth number is the stars after the k−1th bar.
2. What is the number of ways to produce a sequence of numbers 0 < x1 < x2 < · · ·< xk < n?
Answer:
(n−1
k
)
. This is choosing a subset of n−1 numbers without replacement.
3. What is the number of ways to produce a sequence of numbers 0≤ x1 ≤ x2 ≤ ·· · ≤ xk < n?
Answer:
(k+n−1
n−1
)
. We have k dollars to distribute to n boxes.
4. What is the number of poker hands that have at least 1 ace? (Recall that a poker hand is 5 cards from
a 52 card deck.)
Answer:
(52
5
)
−
(48
5
)
. The latter term is the number of poker hands without an ace.
8. Probability Pts: 3/3/3/2/2/2/2/4/2/2/2/2
1. Consider rolling two six sided fair dice.
(a) What is the probability that exactly one die is 6?
Answer: 10/36. There are five ways where the first die is 6 and the second is not, and five more
vice versa.
(b) What is the probability that the sum of the two dice is 6?
Answer: 5/36. The first die, could be 1, . . . ,5, and the other is determined for each first one.
(c) What is the probability that the sum is 6 given that at least one die is at least 3?
Answer: 5/32. There are 4 ways where both die are less than 3, and there are 5 ways where the
sum of the die is 6.
(d) The event of rolling a 6 on the first die is independent of the event that the dice sum to 7.
Answer: True. 1 out of the six ways to get a sum of 7 is the same is 6/36 ways overall.
(e) The event of rolling at least one 6 is independent of the event that the dice sum to 7.
Answer: False. The probability of at least one 6 is 11/36 and the probability of getting at least
one 6 when the die sum to 7 is 1/3.
2. Flip a coin until you repeat either heads or tails 2020 times. We will derive the probability that the first
coin is the same as the last coin in the entire sequence of flips.
(a) If the process stops after 2020 tosses, what is the probability that the first and last coin are the
same?
Answer: 1
(b) If the process stops after 2021 tosses, what it the probability that the first and last coin are the
same?
Answer: 0
(c) What is the probability that the first coin is the same as the last coin in the entire sequence of flips?
Answer: 1/2+ 2−2021. It 1× 2× 1/(2)2020 + 0× 2× (1/2)−2021 +(1/2)2(1− 2× (1/2)2020− 2×
(1/2)2021)
3. Which of the following are always true.
(a) E[10X ] = 10E[X ]
Answer: True. Linearity of expectation is E[aX +b] = aE[X ]+b.
(b) E[X2] = E[X ]2
Answer: False. This is not true in general.
5
SID:
(c) E[(X−Y )2] = E[X2]+E[Y 2]−2E[X ]E[Y ]
Answer: False. Can’t distribute linearity of expectation over term E[XY ].
(d) Var(X +Y ) =Var(X)+Var(Y )
Answer: False. This is not always true, e.g, if Y = X , Var(2X) = 4Var(X) 6= 2Var(X)
9. Marbles: Pts: 4/4
Consider two bags of marbles, the “majority red” bag has 6 red marbles and 4 blue marbles, and the “majority
blue” bag has 3 red marbles and 7 blue marble, and each bag is chosen with probability 1/2.
1. If you draw a blue marble where each marble in the bag is equally likely, what is the probability that
the bag is the “majority blue” bag.
Answer: 7/11. A - event it is majority blue. B is get a blue marble. Notice that each of the marbles is
equally likely to be chosen since each bag is chosen with equal probability.
Thus Pr[B] is 11/20 since there are 11 blue marbles out of 20 marbles. And Pr[A∩B] is 7/20 as there
are 7 blue marbles in the “majority blue” bag out of 20.
Thus, Pr[A|B] = Pr[A∩B]Pr[B] = 7/11.
2. What is the probability that the next marble is blue?
Answer: Use total probability (or thinking about cases!) Let N be the event ’next blue’.
Pr[N] = Pr[N|A]Pr[A]+Pr[N|A]Pr[A] = 69
7
11 +
3
9
4
11 = 54/99 =
6
11 .
10. Variance, covariance, tail bounds.Pts: 3/3/3/3/3
1. If E[X ] = 4, and E[Y ] = 5, and E[XY ] = E[X ]E[Y ], what is cov(X ,Y )?
Answer: 0. cov(X ,Y ) = E[(X − E[X ])(Y − E[Y ])] = E[XY ]− 2E[X ]E[Y ] + E[X ]E[Y ] = E[XY ]−
E[X ]E[Y ] = 0.
2. A student earns one standard deviation above the mean on both exam 1 and exam 2. We define random
variables X and Y as the score of a randomly chosen student on exam 1 and exam 2 respectively. If
Var(X) = 1, Var(Y ) = 1 and Cov(X ,Y ) = .5, how many standard deviations above the mean did the
student get on the sum of her two scores? (Recall, Var(X +Y ) =Var(X)+Var(Y )+2Cov(X ,Y ). )
Answer: 2/
√
3 . The student value is 2 over the sum of the means, and the variance is 3 of the sum
of the random variables, so the standard deviation is 2/
√
3.
3. For a random variable, X , where X ≥−1, E[X ] = 5, and E[X2] = 26. Give an upper bound Pr[X ≥ 6].
(It should be tight with respect to the appropriate inequality.)
Answer: 6/7. One can use Markov’s inequality on the random variable X +1.
4. For a random variable, X , where E[X ] = 5, and E[X2] = 26, give an upper bound Pr[X ≥ 9]. (It should
be tight with respect to the appropriate inequality.)
Answer: 116 .
Chebyshev gives Pr[(X−E(X))≥ 4)≤ Pr[|X−E[X ]| ≥ 4]≤ E[X
2]−E[X2]
16 =
1
16 .
5. Let X be E[X ] = 10 and Var[X ] = σ2. Let Y = X1+···+Xnn where Xi are i.i.d samples of X , for what value
of n is Pr[|Y −E[X ]| ≥ 1.0] ≤ .05? (Provide a bound that is as tight as possible using Chebyshev’s
inequality.)
Answer: n ≥ 20σ2. The variance of Y is σ2/n, and thus Pr[|Y −E[X ]| ≥ 1.0] ≤ Var(Y )1.0 =
σ
2
1.0n ≤ .05
Thus, n≥ σ
2
0.05 = 20σ
2.
6
SID:
11. Continuous: warmup. Pts: 2/2/2/3/3
Consider a continuous random variable, X , with pdf f (x). (Answers below are a number or possibly expres-
sions that involve the random variable and E[·] or Var[·].)
1. What is
∫
∞
−∞ f (x)dx ?
Answer: 1. By definition of a probability density function.
2.
∫
∞
−∞ x f (x)dx?
Answer: E[X ]. By definition of expectation.
3.
∫
∞
−∞ x
2 f (x)dx ?
Answer: E[X2]. Using the E[g(x)] for g(x) = x2.
4. Consider Y = 2X where X ∼ Expo(λ ), Y ∼ Expo(λ ′), what is λ ′?
Answer: λ/2. We stated it was exponential and the expectation must double, so the parameter halves.
5. Recall that for choosing a uniform point in a unit square the pdf is f (x,y) = 1 in the unit square and
zero elsewhere. What is the pdf for choosing a uniform point in a 2× 2 square? (Answer need only
state the pdf inside the 2×2 square as outside it is zero.)
Answer: 14 . The density drops by the factor that the area grows by.
12. Distributions: continuous and discrete. Pts: 3/3/3/3/3/3/1/3
1. Given X ,Y ∼ Binomial(n, p) what is the variance of X +Y ?
Answer: 2np(1− p). X +Y ∼ Binomial(2n, p) if they are independent.. Technially the correct answer
is 2np(1− p)+2(E[XY ]− (np)2).
2. What is E[min(X ,Y,Z)] where X ,Y,Z ∼ Geometric(p)?
Answer: 11−(1−p)3 .
Let M = min(X ,Y,Z), Pr[M ≥ i] = Pr[X ≥ i,Y ≥ i,Z ≥ i] = (1− p)3(i−1).
The tail sum for expectation gives ∑∞1 r
i−1 for r = (1− p)3 which is 11−r .
3. What is E[min(X ,Y,Z)] where X ,Y,Z ∼ Expo(λ )?
Answer: 13λ . Let M = min(Y,X ,Z), Pr[M > x] = Pr[X > x,Y > x,Z > x] = (e
λx)3.
This tells us the distribution is Expo(3λ ).
4. Let Z ∼ Expo(λ ) and Y = dZe (where dxe is the lowest integer of value at least x). Note that the
variable Y ∼ Geometric(p). What is the value of p in terms of λ?
Answer: Y ∼ G(e−λ )).
Pr[Z ∈ [i, i+1]|Z ≥ i] = Pr[Z ∈ [0,1]] = 1− e−λ by the memoryless property.
5. Let Y ∼ Expo(λ ), what is the conditional probability density function of Y if Y ∈ [i, i+1] for a natural
number i in the range [i, i+1]?
[A] λe
−λ (x)
e−λ i
[B] λe
−λ (x)
(1−e−λ ) [C]
λe−λ (x−i)
(1−e−λ ) [D]
λe−λ (x−i)
e−λ (1−e−λ ) [E]
λe−λ (x−i)
(1−e−λ )i
Answer: λe
−λ (x−i)
(1−e−λ ) .
An simple way to see this is the memoryless property: it is the same as the conditional distribution of
being in [0,1] but the variable needs to be shifted into that range. This gives e−λy/(1− e−λ ) and then
use y = (x− i).
Alternative solution. One can also do the calculuation as follows.
Pr[Y ∈ [i, i+1]] = Pr[Y ≤ i+1]−Pr[Y ≤ i] = (1− e−λ (i+1))− (1− e−λ (i)) = e−λ (i)(1− e−λ )
7
SID:
and
Pr[Y ∈ [x,x+dx]|Y ∈ [i, i+1]]≈ λe
λ (x)dx
eλ (i)(1−e−λ if x ∈ [i, i+1].
And we remove the dx to get the density.
6. For X ∼ Geometric(p) and Y ∼ Poisson(X), what is E[Y ]?
Answer: 1p . ∑x(∑y yPr[Y = y])(1− p)
x−1 p = ∑x(∑y yPr[Y = y])(1− p)x−1 p = ∑i i(1− p)i−1 p = 1p
7. Consider a random variable X = 2lnY where Y ∼U [0,1].
(a) What is the range of X? (The range is where the pdf of X is positive.)
Answer: [−∞,0]. For lnx has range [−∞,0] for x ∈ [0,1]
(b) What is the pdf of X on the range defined above? (Hint: Pr[X ∈ [x,x+dx]] =Pr[Y ∈ [ex/2,e(x+dx)/2]
and ex+dx ≈ ex(1+dx))
Answer: e
x/2
2 . Pr[Y ∈ [e
x/2,(1+dx/2)ex/2]]≈ 12 e
x/2dx since Y ∼U [0,1].
Thus, the pdf for X is ex/2/2. One can confirm that
∫ 0
−∞
1
2 e
x/2dx = 1.
13. Continuous: Triangle. Pts: 2/3/3/2
Consider a right equilateral triangle of side lengths 1,1 and
√
2. Given a random point in the triangle, we
define the random variable X as the distance from the hypotenuse as shown in the figure below.
X
1. What is the joint density function f (x,y) for points inside the triangle? (Again, the point is chosen
uniformly inside the entire triangle. Ignore the shading in the figure for now.)
Answer: 2. Note the area of the triangle is 1/2, thus the density per unit area is 2.
2. What is the area of the shaded triangle in terms of X? (Hint: range of X is [0,
√
2/2])
Answer: (1−
√
2x)2
2 . The sidelength is 1− x
√
2.
3. What is the cdf of X for the range x ∈ [0,
√
2/2]?
Answer: 1− (1−
√
2x)2.
The points that are farther than x away from the hypotenuse are in the shaded triangle. The density is
2, which we multiply be the area of the shaded.
You take the complement to get the cdf.
4. What is the pdf of X for the range x ∈ [0,
√
2/2]?
Answer: 2
√
2(1−
√
2x). Take the derivative of the cdf.
14. Markov Chain. Pts: 2/2/2/2
Consider the following Markov chain.
8
SID:
1
2
3
1−a 1
1
a
1. For what value of a does the chain have a unique invariant distribution but does not always converge
to it.
Answer: a = 0.0. In this case there is one cycle of length 3, and the period is 3.
2. For a = 1/2, what is the stationary distribution?
π(1): π(2): π(3):
Answer: π(1) = 1/2,π(2) = π(3) = 1/4
Let x = π(1), π(3) = π(2) = (1−a)x. And x+2(1−a)x = 1.0, which means x = 1.0/(3−2a).
Long Answers Starting From here.
15. Small faces. Pts: 2/2/4
Given a planar graph with minimum degree 3 with e edges, v vertices and f faces we will prove there is a
face of length at most 5. (The length of a face is the number of edges along it.)
1. What is the sum of the face lengths, ∑
f
i=1 si where si is the size of face i, in terms of e?
Answer: 2e. Each face is adjacent to si edges, and each edge is adjacent to 2 faces.
2. Give a lower bound on e in terms of v. (Hint: the minimum degree is 3.)
Answer: Recall 2e = ∑v d(v)≥ 3v, or e≥ 32 v.
3. Prove that there is a face of size at most 5. (Recall: Euler’s formula v+ f = e+2.)
Answer: Assume that every face has length at least 6.
2e = ∑i=0 si ≥ 6 f . or 13 e≥ f
And
v+ 13 e≥ e+2 or v≥
2
3 e+2≥ v+2. This is a contradiction.
16. Balls and Bins.Pts: 3/3/2/2
Consider placing 5n balls into 3n bins uniformly at random. (Careful, the constants in front of the n’s are
important.)
1. What is the expected number of empty bins?
Answer: 3n(1− 13n)
5n. The probability that a bin is empty is (1− 13n)
5n and then use linearity of
expectation.
2. What is the variance of the number of empty bins?
Answer: 3n(1− 13n)
5n +2
(3n
2
)
(1− 23n)
5n− (3n(1− 13n)
5n)2
Let Xi be an indicator random variable for the ith bin being empty.
E[(X1 + · · ·X3n)2] = ∑i X2i +∑i j XiX j = 3n(1−
1
3n)
5n +2
(3n
2
)
(1− 23n)
5n
3. What is the expected number of non-empty bins?
Answer: 3n(1− (1− 13n)
5n). This is just 3n−X where X is the number of empty bins.
9
SID:
4. What is the variance of the number of non-empty bins (in terms of the answer for part (1),(2) and/or
(3).)
Answer: Same as b. The Var(3n−X) =Var(X).
17. Sequential Dice.Pts: 3/3/3
Consider rolling a dice repeatedly and until one gets two 6’s in a row.
1. Draw a three state Markov chain where the states are labelled A,B, and C. Your chain should have a
state C which is the “goal”; the previous two rolls were a 6. State A should indicate that one has not
rolled any die or that the previous die is not 6.
Answer:
A
5/6
B
C
1/6 1/6
5/6
5/6
1/6
2. What is the expected number of rolls to roll two 6’s in a row?
Answer: 42.
β (a) = 1+ 16 β (b)+
5
6 β (a)
β (b) = 1+ 56 β (a)
Thus,
β (a) = 1+ 16(1+
5
6 β (a))+
5
6 β (a)
And, β (a) = 42.
3. What is the probability of rolling two 6’s in a row prior to rolling a 5? (Hint: add a state to your
previous Markov Chain and do a computation.)
Answer: 1/8.
Add a state D with transition probabitiy from A and B of 1/6.
α(a) = 2/3α(a)+1/6α(b)
α(b) = 2/3α(a)+1/6
Thus, α(a) = 7/9α(a)+1/36 and α(a) = 1/8.
18. Bayes Rule. Pts: 5
A doctor has information that 80% of the sick children in a neighborhood have the flu and the other 20%
of sick children have measles. He further knows that the probability of a rash with measles, is 0.95, and
that the probability of a rash with flu is .10. If a sick child has a rash, what is the probability the child has
measles. (Show your work here. And use the box for your final answer.)
Answer: 19/27.
Pr[M|R] =
Pr[R|M]×Pr[M]
Pr[R|M]×Pr[M]+Pr[F |R]×Pr[R]
=
.2∗ .95
.2+ .10× .8
=
19
27
.
10
SID:
19. Close enough! Pts: 5
Given a circle (dartboard) of radius 1, choose two points at random on the dartboard uniformly, and let X
and Y define the distance to the center. What is the probability that |X−Y | ≤ δ? (Recall that the pdf of both
variables is f (x) = 2×1{x < 1} )
Answer: 4(1−δ )
3
δ
3 −2δ (1−δ )
2.
We compute the probability that X ≤ Y and |Y −X |< δ .∫ 1−δ
0 2x
∫ x+δ
x 2ydydx+
∫ 1
1−δ 2x
∫ 1
x 2ydydx
=
∫ 1−δ
0 2x((x+δ )
2− x)dx+
∫ 1
1−δ (1− x
2)dx
=
∫ 1−δ
0 2x(2δx+δ
2)+(x− x
3
3 )|
1
1−δ
= 2δx
3
3 −δx
2|1−δ0 +(δ −
1
3 +
(1−δ )3
3
=
2δ (1−δ )3
3 −δ (1−δ )
2 +δ − 13 +
(1−δ )3
3
= δ (1−δ )3−δ (1−δ )2 +δ − 13
FIXME...
2
(
δ
4
6 −δ
2 + 4δ3
)
We double since the Y ≤ X case is symmetric.
20. Puzzler: Pts: 3/5
Consider the following game on an n×m grid, with two cooperating players. A key is hidden under a grid
square and on each square there is a single coin that is either heads or tails. Player 1 knows the key location
and must flip exactly one coin.
Player 2 should observe the pattern of heads and tails and produce the key location.
To reiterate, from an arbitrary initial setup of heads and tails on the grid, player 1 should flip exactly one
coin to make a setup where player 2 can determine the location of the hidden key.
1. What is a strategy for the players to win on a 2× 1 grid? (Hint: Think about 2x+ y (mod 2) for
x,y ∈ {0,1} and think of heads as 1 and 0 as tails.)
Answer: Let’s x = 1 if the left square is heads, and y = 1 if the right one is. Consider the z = 2x+ y
(mod 2). The players agree that if z = 1, the key is in the left square, otherwise it is in the right one.
Notice if the value of z in the initial configuration is correct changing the value of x does not change
the value of z, so Player 1 can flip the coin in the first square, if initial value of z was incorrect, Player
1 can flip the coin in the right square and change it.
2. What is a strategy for the players to win on a 2k×2k grid? (Hint: use induction to find the column and
row of the coin to flip. Notice, 2k = (2× (2×2k−1).)
Answer:
Break up the grid into 4 subgrids of size 2k−1×2k−1.
Then one can use a 2×2 grid using part (a) to figure out the column.
One takes the parity of the number of heads in each subgrid to be a proxy for flipping one coin, as
flipping any coin in that subgrid flips the parity.
Now the 2×2 grid can be done, by taking parity of columns and using part (a) to determine the column
and then to recursively choose the bit in the column to determine the row.
11
SID:
Thus, at the top level one has a 2×2 instance.
Then recurse on the quadrant that is indicated by the 2×2 instance which is now a 2k×2k.
Another solution is to consider reorganize into a 2× 22k−1 grid, and taking the parity of the columns
to indicate the column, and then using that column recursively using the 2×1 solution in part (a).
12