Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 70

Discrete Mathematics and Probability Theory

Spring 2023

Final

2. Propositions. Other stuff.

1. False =⇒ False.

True     False

2. False =⇒ True.

True     False

3. (¬(∃x ∈ S)(P(x))) =⇒ (∀x ∈ S)(P(x) =⇒ Q(x))

Always True.     Sometimes False.

4. (∀x ∈ S)(∃y ∈ S)(Q(x, y) =⇒ P(x)) ≡ (∀x ∈ S)(¬P(x) =⇒ ¬(∀y ∈ S)(Q(x, y)))

Always True.     Sometimes False.

5. In any stable matching instance, there is no stable pairing where every job gets its least favorite candi-date.

True     False

6. If the propose-and-reject algorithm with jobs proposing terminates on the first day, then the matching is both job-optimal and candidate-optimal.

True     False

3. Quick proofs.

1. Prove or disprove: For x, y ∈ N where x ≤ y, then either x ≤ y/2 or y−x ≤ y/2.

2. Consider the equation b2 = 3a2.

(a) What is the number of solutions for the equation for a,b ∈ N? (Your answer should possibly be a natural number or infinity.)

(b) (5 points) Give a proof for your answer.

4. Mods.

1. If f(x) = ax (mod p) where a ≠ 0, p is prime, and gcd(a, p) = 1, what is the size of the following set:

{ f(0) mod p,..., f(p−1) mod p}

(Answer could be in terms of p.)

2. If f(x) = ax (mod N) where N > 1 and gcd(a,N) = d, what is the size of the following set:

{ f(0) mod N,..., f(N −1) mod N}

(Answer could be in terms of a, d and N.)

3. What is the product of the numbers 12, 22, . . . , (p−1) 2 modulo p for a prime p? (Answer could be a number or an expression involving p.)

5. Quick Bayes.

(5 points) I pick one of two dice with equal probability: one die is a tetrahedron with 1, 2, 3, 4 on the four sides, and one die is a six sided die with 1, 2, 3, 4, 5, 6 on the sides. When rolling a die, all sides are equally likely.

Suppose I roll a 3. What is the probability that I rolled the tetrahedron? (Show work if desired, but clearly indicate final answer.)

6. Graphs with friends.

Consider a process with n ≥ 7 people where each person i arrives and chooses min(i,7) different people from {0,...,i−1} to be friends with (and everyone accepts those friendships). Consider the resulting (undirected) graph G, where vertices correspond to the n people, and edges correspond to the friendships among these n people.

1. What is the total number of edges in the graph? (Answer could be a number or an expression involving n.)

2. What is the maximum possible degree of any vertex in any such graph G? (Answer could be a number or an expression involving n.)

3. (a) What is the minimum number of colors required to vertex color any n vertex graph that results from this process? (Answer could be a number or an expression involving n.)

(b) (5 points) Give a proof for your answer to the previous part.

4. If each person i chooses a random subset of min(7,i) previous people to be friends with, what is the expected degree of person 0? (Answer is in terms of n, and uses a summation.)

7. More Graphs

1. A hypercube of dimension 3 has more edges than K4.

True     False

2. What is the maximum number of vertices in a graph with e edges and c connected components?

(Answer could be in terms of e and/or c.)

3. The number of odd degree vertices in any graph is odd.

True     False

4. What is the average degree of an n vertex tree? (The answer should be in terms of n and should be exact.)

5. (5 points) For a planar graph on v vertices with a planar drawing where the average number of sides on each face is s, what is the total number of edges? (Recall that Euler’s formula is v+ f = e+2. Answer should be in terms of only v and s and not use f .)

8. Polynomials.

1. Consider a polynomial P(x) of degree 2 under arithmetic modulo 7, where

P(0) ≡ 0   (mod 7)

P(1) ≡ 2   (mod 7)

P(6) ≡ P(−1) ≡ 2   (mod 7)

(a) If P(x) = (x−6)Q(x) +r, what is r?

(b) What is P(x)?

(c) Suppose a degree 0 polynomial, Q(x), differs from P(x) on one of the given points. What is Q(x)?

2. Given a polynomial P(x) of degree 2 with P(0) = 0, P(1) = P(−1) = A, what is P(x) in terms of A?

3. Consider a polynomial P(x) of degree d modulo a prime p. How many polynomials Q(x) of degree at most d satisfy P(1) = Q(1), P(2) = Q(2), . . . , P(k) = Q(k)? (You may assume k ≤ d and that p ≥ d +1 and P(x) itself should be counted.)

9. Countability/Computability.

1. For any two distinct real numbers in [0,1], there is a rational in between them.

True     False

2. The cardinality of the rational numbers is equal to the cardinality of the set of pairs of real numbers in [0,1].

True     False

3. The number of computer programs is countable.

True     False

4. The number of outputs for any computer program on any finite length input is countable. (Note that the output of a computer program could be an infinite sequence of digits, for example, a square root program could run forever while printing the digits of √ 2.)

True     False

5. There is a program P such that on inputs Q and x, P(Q, x) halts if and only if the program Q does not halt on input x.

True     False

10. Counting: Warmup

1. What is the number of 2 element subsets of a set of n distinct items?

2. What is the number of non-empty subsets of a set of n distinct items?

3. What is the number of orderings of k distinct items?

4. How many Hamiltonian paths are there on Kn?

5. How many Hamiltonian cycles are there on Kn?

11. Stirling numbers.

Stirling numbers are numbers S(n, k) which denote the number of partitions of an n-element set into k non-empty subsets. For example, S(4,2) = 7, because there are 7 different partitions of a 4-element set {1,2,3,4} into 2 subsets:

{1}{2,3,4} {1,2}{3,4} {4}{1,2,3} {1,4}{2,3} {2}{1,3,4} {1,3}{2,4} {3}{1,2,4}

Note that the partition order does not matter; that is, {1,2}{3,4} is equivalent to {3,4}{1,2}.

1. Find a formula for S(n,n−1).

2. Find a formula for S(n,2).

3. (10 points) Prove that S(n+1, k) = k · S(n, k) +S(n, k −1) using a combinatorial proof.

4. (5 points) How many ways can you select n numbers without order and with repetition from the set {1,2,...,m}, such that there are exactly k distinct values among the numbers selected? Hint: this does not involve Stirling numbers.

5. (5 points) How many ways can you select n numbers with order and with repetition from the set {1,2,...,m}, such that there are exactly k distinct values among the numbers selected? Express your answer in terms of the Stirling numbers.

12. Tails, tails, and tails.

Suppose Shreyas stores some number S initialized to 0. Every time he flips a fair coin, if it lands heads he increments S by 1 and if it lands tails he decrements S by 1. He wishes to calculate P[S ≥ 20] after flipping the coin 100 times.

1. (5 points) Provide an exact answer using a summation. (Hint: S ≥ 20 is equivalent to saying that Shreyas flips 20 more Heads than Tails.)

2. (5 points) Provide an upper bound using Markov’s inequality.

3. (5 points) Provide an upper bound using Chebyshev’s inequality.

4. (5 points) Provide an upper bound using the Central Limit Theorem. (Leave your answer in terms of Φ, where Φ is the standard Normal CDF, if you deem necessary.)

13. Uniform parameter for a geometric distribution.

Suppose Jonathan picks a real number R uniformly at random from the range [0.25,0.75]. Then, he takes a coin that yields heads with probability R and tails otherwise and flips it until it yields heads. Let J denote the number of flips (including the last flip that yields heads).

1. What is E[R]?

2. (5 points) Compute E[J]. Show your work and clearly indicate your final answer.

3. Compute P[J > 70 | R = r].

4. (5 points) Compute P[J > 70]. Show your work and clearly indicate your final answer. (The answer is a bit messy.)

14. How many? And for how long?

(6 points) You purchase a box of light bulbs where the number of light bulbs is a Poisson random variable, N ∼ Poisson(µ).

Let the random variable Xi denote the lifetime of the i th bulb. The lifetimes of the bulbs are independent.

Moreover, each Xi obeys the exponential distribution

where λ > 0.

Determine a reasonably-simple expression for E[T], the expected total life that you can get from the light bulbs in your box. Your expression must be in closed form, and involve nothing other than a subset of the parameters λ and µ.

Note that

T = X1 +···+XN,

where N is the random variable for the number of light bulbs in the box.

15. Just a moment or three.

Let X ∼ N (µ,σ2).

1. Compute E[X].

2. Compute E[X 2 ].

3. (5 points) Compute E[X 3 ]. Hint: (a+b)3 = a3 +3a2b+3ab2 +b3.

16. Joint Pizza Social.

Jonathan is taking some CS 70 staff members to a pizza social. However, he is unsure of how many staff members will show up! Let S be the number of staff members who show up and let P be the number of pizzas Jonathan orders. The joint distribution of S and P is given by the following table:

1. Compute the marginal distributions of S and P.

2. Compute E[S] and E[P].

3. Compute P[S = P].

4. Compute P[S = 3 | S ≥ P].

17. Indicators to an inequality.

A Bernoulli random variable IA—called the indicator of event A—maps each sample point ω in the sample space Ω to either 0 or 1 according to the following rule:

To avoid clutter, we often omit the dependence on ω, and write IA = 1 if “A happens (or A is true),” and IA = 0 if “A does not happen (or A is not true).” Clearly, P[{IA = 1}] = P[A].

Indicators for other events are defined in a similar fashion.

1. Show that E[IA] = P[A].

2. Consider two events A and B and their corresponding indicators IA and IB.

(a) Show that

IAIB = IA∩B = min(IA,IB).

(b) Show that

IA∪B = IA +IB −IA∩B = max(IA,IB).

(c) (5 points) Show that the indicators IA and IB are uncorrelated if and only if the events A and B are independent.

3. (8 points) Let α1,...,αn ∈ R be arbitrary (possibly negative) constants, and let A1,...,An denote arbi-trary events in a sample space Ω.

Show that

Hint: Let IA1 ,...,IAn denote the indicators for A1,...,An, respectively. Then, take advantage of the fact that

to progress toward the unintuitive result of Equation (1).

18. Probability Mass Function.

The probability mass function of a discrete random variable M is

Here, α is a constant.

In what follows, you may or may not find the following facts useful:

Sum of the First n Positive Integers:

Sum of the Squares of the First n Positive Integers:

1. Determine α.

Your answer must be a reasonably simple expression in terms of n.

2. Determine E[M]. Leave your result here in terms of α.

3. Determine the cumulative distribution function of M, defined by

∀m ∈ Z,      FM(m) = P[M ≤ m].

Leave your result here in terms of α.

19. Spinning Laser. (Watch your eyes!)

A rotatable bidirectional laser is anchored at the point (−1,0) in the xy-plane. We spin the laser and let it come to rest at a uniformly-random angle Θ, where the angle is measured in reference to the positive direction of the x-axis, as shown in the diagram below. Accordingly, Θ is distributed uniformly between −π/2 and π/2.

The random variable Y denotes the corresponding point of incidence of the laser beam on the vertical axis.

1. The random variable Y is a function of the random variable Θ. So, first, determine a simple expression for Y in terms of Θ.

2. Determine a reasonably simple expression for the cumulative distribution function (CDF) of Y, defined by

FY (y) = P[Y ≤ y].

3. Determine a reasonably simple expression for the PDF fY (y). In doing so, and depending on how you tackle the problem, you may or may not find it useful to know that

20. Confused Concierge.

Four guests G1,...,G4 leave their umbrellas with Babak, the concierge at Hotel Satish. Babak is absent-minded and mixes up the umbrellas uniformly at random when handing them back to the guests.

We will determine P[C], the probability that Babak returns at least one umbrella to its rightful owner.

Let Cℓ denote the event that Babak returns the correct umbrella to guest Gℓ , where ℓ ∈ {1,2,3,4}.

Recall the Inclusion-Exclusion Principle for n events C1,...,Cn:

For n = 2, the inclusion-exclusion principle translates to

P[C1 ∪C2] = P[C1] +P[C2]−P[C1 ∩C2].

For n = 3, the inclusion-exclusion principle translates to

P[C1 ∪C2 ∪C3] = P[C1] +P[C2] +P[C3]

−P[C1 ∩C2]−P[C1 ∩C3]−P[C2 ∩C3]

+P[C1 ∩C2 ∩C3].

You need not write all the terms for the case n = 4, because there are too many. Instead, use the structures of the n = 2 and n = 3 cases to construct in your mind the general structure of the types of terms involved in the case n = 4.

1. What is P[C1]?

2. Using a single word, explain why P[Ci ] = P[Cj ] for all i, j ∈ {1,2,3,4}.

3. Using inclusion/exclusion, how many terms of the type P[Ck ∩Cℓ ] are there?

4. (5 points) Compute the probability that at least one guest gets their umbrella back. Show your work, but clearly indicate your final answer.

21. Balls and Bins.

Leanne throws n distinct balls into n distinct bins, labeled 1,2,...,n. Let X represent the number of ordered pairs (i,i+1) of bins, for 1 ≤ i ≤ n−1, such that bin i and bin i+1 are both empty.

1. (5 points) What is E[X]? Show your work, but clearly indicate your final answer.

2. (10 points) What is Var(X)? Show your work, but clearly indicate your final answer.