CS70-Homework 0 Solved

Classify the following statements as being one of the following, where x and y are arbitrary propositions, and justify your answers (e.g., using a truth table)

True for all combinations of x and y (Tautology)
False for all combinations of x and y (Contradiction)
Neither
x∧(x =⇒ y)∧(¬y)
x =⇒ (x∨y)
(x∨y)∨(x∨¬y)
(x =⇒ y)∨(x =⇒ ¬y)
(x∨y)∧(¬(x∧y))
(x =⇒ y)∧(¬x =⇒ y)∧(¬y)
2      Miscellaneous Logic
Let the statement, (∀x ∈ R)(∃y ∈ R) G(x,y), be true for predicate G(x,y).
For each of the following statements, decide if the statement is certainly true, certainly false, or possibly true, and justify your solution. (If possibly true, provide a specific example where the statement is false and a specific example where the statement is true.)

G(3,4)
(∀x ∈ R) G(x,3)
∃y G(3,y)
∀y ¬G(3,y)
∃x G(x,4)
Give an expression using terms involving ∨,∧ and ¬ which is true if and only if exactly one of X,Y, and Z is true.
3       Propositional Practice
Convert the following English sentences into propositional logic and the following propositions into English. State whether or not each statement is true with brief justification.

There is a real number which is not rational.
All integers are natural numbers or are negative, but not both.
If a natural number is divisible by 6, it is divisible by 2 or it is divisible by 3.
(∀x ∈ R)(x ∈ C)
(∀x ∈ Z)(((2 | x)∨(3 | x)) =⇒ (6 | x)) (f) (∀x ∈ N)((x 7) =⇒ ((∃a,b ∈ N)(a+b = x)))
4      Proof by?

Prove that if for any two integers x and y, if 10 does not divide xy, then 10 does not divide x and 10 does not divide y. In notation: (∀x,y ∈ Z) (10 - xy) =⇒ ((10 - x) ∧ (10 - y)). What proof technique did you use?
Prove or disprove the contrapositive.
Prove or disprove the converse.
5      Prove or Disprove
(∀n ∈ N) if n is odd then n2 +2n is odd.
(∀x,y ∈ R) min(x,y)=(x+y−|x−y|)/
(∀a,b ∈ R) if a+b ≤ 10 then a ≤ 7 or b ≤
(∀r ∈ R) if r is irrational then r+1 is irrational.
(∀n ∈ Z+) 10n2 n!.
6       Preserving Set Operations
For a function f, define the image of a set X to be the set f(X)= {y | y = f(x) for some x ∈ X}. Define the inverse image or preimage of a set Y to be the set f−1(Y)= {x | f(x) ∈ Y}. Prove the following statements, in which A and B are sets. By doing so, you will show that inverse images preserve set operations, but images typically do not.

Hint: For sets X and Y, X =Y if and only if X ⊆Y and Y ⊆ X. To prove that X ⊆Y, it is sufficient to show that (∀x)((x ∈ X) =⇒ (x ∈Y)).

(a) f−1(A∪B)= f−1(A)∪ f−1(B). (b) f−1(A∩B)= f−1(A)∩ f−1(B).

f−1(A\B)= f−1(A)\ f−1(B).
f(A∪B)= f(A)∪ f(B).
f(A∩B) ⊆ f(A)∩ f(B), and give an example where equality does not hold.
f(A\B) ⊇ f(A)\ f(B), and give an example where equality does not hold.
 

 

State which of the proofs below is correct or incorrect. For the incorrect ones, please explain clearly where the logical error in the proof lies. Simply saying that the claim or the induction hypothesis is false is not a valid explanation of what is wrong with the proof. You do not need to elaborate if you think the proof is correct.

Claim: For all positive numbers n ∈ R, n2 ≥ n.
Proof. The proof will be by induction on n.

Base Case: 12 ≥ 1. It is true for n = 1.

Inductive Hypothesis: Assume that n2 ≥ n.

Inductive Step: We must prove that (n+1)2 ≥ n+1. Starting from the left hand side,

(n+1)2 = n2 +2n+1 ≥ n+1.

       Therefore, the statement is true.                                                                            

Claim: For all negative integers n, (−1)+(−3)+···+(2n+1)= −n2.
Proof. The proof will be by induction on n.

Base Case: −1 = −(−1)2. It is true for n = −1.

Inductive Hypothesis: Assume that (−1)+(−3)+···+(2n+1)= −n2.

Inductive Step: We need to prove that the statement is also true for n−1 if it is true for n, that is, (−1)+(−3)+···+(2(n−1)+1)= −(n−1)2. Starting from the left hand side,

(−1)+(−3)+···+(2(n−1)+1)=((−1)+(−3)+···+(2n+1))+(2(n−1)+1)

= −n2 +(2(n−1)+1) (Inductive Hypothesis)

= −n2 +2n−1

= −(n2 −2n+1) = −(n−1)2.

       Therefore, the statement is true.                                                                            

(c) Claim: For all nonnegative integers n, 2n = 0.

Proof. We will prove by strong induction on n.

Base Case: 2×0 = 0. It is true for n = 0.

Inductive Hypothesis: Assume that 2k = 0 for all 0 ≤ k ≤ n.

Inductive Step: We must show that 2(n+1)= 0. Write n+1 = a+b where 0 < a,b ≤ n. From the inductive hypothesis, we know 2a = 0 and 2b = 0, therefore,

2(n+1)= 2(a+b)= 2a+2b = 0+0 = 0.

       The statement is true.                                                                                             

2       A Coin Game
Your "friend" Stanley Ford suggests you play the following game with him. You each start with a single stack of n coins. On each of your turns, you select one of your stacks of coins (that has at least two coins) and split it into two stacks, each with at least one coin. Your score for that turn is the product of the sizes of the two resulting stacks (for example, if you split a stack of 5 coins into a stack of 3 coins and a stack of 2 coins, your score would be 3·2 = 6). You continue taking turns until all your stacks have only one coin in them. Stan then plays the same game with his stack of n coins, and whoever ends up with the largest total score over all their turns wins.

Prove that no matter how you choose to split the stacks, your total score will always be n.

(This means that you and Stan will end up with the same score no matter what happens, so the game is rather pointless.)

3      Grid Induction
Pacman is walking on an infinite 2D grid. He starts at some location (i, j)∈N2 in the first quadrant, and is constrained to stay in the first quadrant (say, by walls along the x and y axes). Every second he does one of the following (if possible):

Walk one step down, to (i, j−1).
Walk one step left, to (i−1, j).
For example, if he is at (5,0), his only option is to walk left to (4,0); if Pacman is instead at (3,2), he could walk either to (2,2) or (3,1).

Prove by induction that no matter how he walks, he will always reach (0,0) in finite time. (Hint: Try starting Pacman at a few small points like (2,1) and looking all the different paths he could take to reach (0,0). Do you notice a pattern?)

4      Stable Marriage
Consider a set of four men and four women with the following preferences:

men
preferences
women
preferences
A
1234
1
DABC
 
1324
2
BC
 
1324
3
BC
D
3124
4
ABDC
Run on this instance the stable matching algorithm presented in class. Show each day of the algorithm, and give the resulting matching, expressed as {(M,W),...}.
Suppose we relax the rules for the men, so that each unpaired man proposes to the next woman on his list at a time of his choice (some men might procrastinate for several days, while others might propose and get rejected several times in a single day). Prove that this modification will not change what pairing the algorithm outputs.
5       Optimal Partners
In the notes, we proved that the Stable Marriage Algorithm always outputs the male-optimal pairing. However, we never explicitly showed why it is guaranteed that putting every man with his best choice results in a pairing at all. Prove by contradiction that no two men can have the same optimal partner. (Note: your proof should not rely on the fact that the Stable Marriage Algorithm outputs the male-optimal pairing.)

6       Examples or It’s Impossible
Determine if each of the situations below is possible with the traditional propose-and-reject algorithm. If so, give an example with at least 3 men and 3 women. Otherwise, give a brief proof as to why it’s impossible.

Every man gets his first choice.
Every woman gets her first choice, even though her first choice does not prefer her the most. (c) Every woman gets her last choice.
Every man gets his last choice.
A man who is second on every woman’s list gets his last choice.
 

 
1       Short Answer: Graphs
Bob removed a degree 3 node in an n-vertex tree, how many connected components are in the resulting graph? (An expression that may contain n.)
Given an n-vertex tree, Bob added 10 edges to it, then Alice removed 5 edges and the resulting graph has 3 connected components. How many edges must be removed to remove all cycles in the resulting graph? (An expression that may contain n.)
True or False: For all n 3, the complete graph on n vertices, Kn has more edges than the n-dimensional hypercube. Justify your answer.
A complete graph with n vertices where n is an odd prime can have all its edges covered with x Hamiltonian cycles (a Hamiltonian cycle is a cycle where each vertex appears exactly once). What is the number, x, of such cycles required to cover the a complete graph? (Answer should be an expression that depends on n.)
Give a set of edge-disjoint Hamiltonian cycles that covers the edges of K5, the complete graph on 5 vertices. (Each path should be a sequence (or list) of edges in K5, where an edge is written as a pair of vertices from the set {0,1,2,3,4} - e.g: (0,1),(1,2).)
2         Eulerian Tour and Eulerian Walk
Is there an Eulerian tour in the graph above?
Is there an Eulerian walk in the graph above?
What is the condition that there is an Eulerian walk in an undirected graph? Briefly justfy your answer.
3       Bipartite Graph
A bipartite graph consists of 2 disjoint sets of vertices (say L and R), such that no 2 vertices in the same set have an edge between them. For example, here is a bipartite graph (with L = {green vertices} and R ={red vertices}), and a non-bipartite graph.

Figure 1: A bipartite graph (left) and a non-bipartite graph (right).

Prove that a graph is bipartite if and only if it has no tours of odd length.

4      Hypercubes
The vertex set of the{and only if      n-dimensional hypercube G = (V,E) is given by V = {0,1}n (xrecall thatand y if

0,1}n denotes the set of allx and y differ in exactly one bit position. These problems will help you understandn-bit strings). There is an edge between two vertices hypercubes.

Draw 1-, 2-, and 3-dimensional hypercubes and label the vertices using the corresponding bit strings.
Show that for any n 1, the n-dimensional hypercube is bipartite: the vertices can be partitioned into two groups so that every edge goes between the two groups.
5        Triangulated Planar Graph
In this problem you will prove that every triangulated planar graph (every face has 3 sides; that is, every face has three edges bordering it, including the unbounded face) contains either (1) a vertex of degree 1, 2, 3, 4, (2) two degree 5 vertices which are adjacent, or (3) a degree 5 and a degree 6 vertices which are adjacent. Justify your answers.

(a) Place a “charge” on each vertex v of value 6 degree(v). What is the sum of the charges on all the vertices? (Hint: Use Euler’s formula and the fact that the planar graph is triangulated.) (b) What is the charge of a degree 5 vertex and of a degree 6 vertex?

Suppose now that we shift 1/5 of the charge of a degree 5 vertex to each of its neighbors that has a negative charge. (We refer to this as “discharging” the degree 5 vertex.) Conclude the proof under the assumption that, after discharging all degree 5 vertices, there is a degree 5 vertex with positive remaining charge.
If no degree 5 vertices have positive charge after discharging the degree 5 vertices, does there exist any vertex with positive charge after discharging? If there is such a vertex, what are the possible degrees of that vertex?
Suppose there exists a degree 7 vertex with positive charge after discharging the degree 5 vertices. How many neighbors of degree 5 might it have?
Continuing from Part (e). Since the graph is triangulated, are two of these degree 5 vertices adjacent?
Finish the proof from the facts you obtained from the previous parts.
 

 

Find all solutions (modulo the corresponding modulus) to the following equations. Prove that there are no other solutions (in a modular setting) to each equation.

2x ≡ 5 (mod 15)
2x ≡ 5 (mod 16) (c) 5x ≡ 10 (mod 25)
2       Euclid’s Algorithm

Use Euclid’s algorithm from lecture to compute the greatest common divisor of 527 and 323. List the values of x and y of all recursive calls.
Use extended Euclid’s algorithm from lecture to compute the multiplicative inverse of 5 mod
List the values of x and y and the returned values of all recursive calls.
Find x (mod 27) if 5x+26 ≡ 3 (mod 27). You can use the result computed in (b).
Assume a, b, and c are integers and c  Prove or disprove: If a has no multiplicative inverse mod c, then ax ≡ b (mod c) has no solution.
3       Modular Exponentiation

Compute the following:

132018 (mod 12)
811111 (mod 9)
7256 (mod 11)
3160 (mod 23)
4       Euler’s Totient Function

Euler’s totient function is defined as follows:

φ(n)= |{i : 1 ≤ i ≤ n,gcd(n,i)= 1}|

In other words, φ(n) is the total number of positive integers less than or equal to n which are relatively prime to it. Here is a property of Euler’s totient function that you can use without proof:

For m,n such that gcd(m,n) = 1, φ(mn)=φ(m)·φ(n).

Let p be a prime number. What is φ(p)?
Let p be a prime number and k be some positive integer. What is φ(pk)?
Let p be a prime number and a be a positive integer smaller than p. What is aφ(p) (mod p)? (Hint: use Fermat’s Little Theorem.)
Let b be a positive integer whose prime factors are p1, p2,..., pk. We can write b p ... pαkk.
Show that for any a relatively prime to b, the following holds:

∀i ∈ {1,2,...,k}, aφ(b) ≡ 1 (mod pi)

5       FLT Converse

Recall that the FLT states that, given a prime n, an−1 ≡ 1 (mod n) for all 1 ≤ a ≤ n−1. Note that it says nothing about when n is composite.

Can the FLT condition (an−1 ≡ 1 mod n) hold for some or even all a if n is composite? This problem will investigate both possibilities. It turns out that unlike in the prime case, we need to restrict ourselves to looking at a that are relatively prime to n. (Note that if n is prime, then every a < n is relatively prime to n). Because of this restriction, let’s define

S(n)= {i : 1 ≤ i ≤ n,gcd(n,i)= 1},

so | S | is the total number of possible choices for a.

Prove that for every a and n that are not relatively prime, FLT condition fails. In other words, for every a and n such that gcd(n,a) 6= 1, we have an−1 ≡6 1 (mod n).
Prove that the FLT condition fails for most choices of a and n. More precisely, show that if we can find a single a ∈ S(n) such that an−1 ≡6 1 (mod n), we can find at least |S(n)|/2 such a. (Hint: You’re almost there if you can show that the set of numbers that fail the FLT condition is at least as large as the set of numbers that pass it. A clever bijection may be useful to compare set sizes.)
The above tells us that if a composite number fails the FLT condition for even one number relatively prime to it, then it fails the condition for most numbers relatively prime to it. However, it doesn’t rule out the possibility that some composite number n satisifes the FLT condition entirely: for all a relatively prime to n, an−1 ≡ 1 mod n. It turns out such numbers do exist, but they were found through trial-and-error! We will prove one of the conditions on n that make it easy to verify the existence of these numbers.

First, show that if a ≡ b mod m1 and a ≡ b mod m2, with gcd(m1,m2) = 1, then a ≡ b (mod m1m2).
Let n = p1p2 ·· pk where pi are distinct primes and pi −1 | n−1 for all i. Show that an−1 ≡ 1 (mod n) for all a ∈ S(n)
Verify that for all a coprime with 561, a560 ≡ 1 (mod 561).
 

 

Simplify each expression using Fermat’s Little Theorem.

333 (mod 11)
1000110001 (mod 17)
1010 +2020 +3030 +4040 (mod 7)
2       RSA Practice

Bob would like to receive encrypted messages from Alice via RSA.

Bob chooses p= 7 and q= His public key is (N,e). What is N?
What number is e relatively prime to?
e need not be prime itself, but what is the smallest prime number e can be? Use this value for e in all subsequent computations.
What is gcd(e,(p−1)(q−1))?
What is the decryption exponent d?
Now imagine that Alice wants to send Bob the message 30. She applies her encryption function E to 30. What is her encrypted message?
                                                                                                                                                                                   1

Bob receives the encrypted message, and applies his decryption function D to it. What is D applied to the received message?
3       Squared RSA

Prove the identity ap(p−1) ≡ 1 (mod p2), where a is coprime to p, and p is prime. (Hint: Try to mimic the proof of Fermat’s Little Theorem from the notes.)
Now consider the RSA scheme: the public key is (N = p2q2,e) for primes p and q, with e relatively prime to p(p− 1)q(q− 1). The private key is d = e−1 (mod p(p− 1)q(q− 1)). Prove that the scheme is correct for x relatively prime to both p and q, i.e. xed ≡x (mod N).
Prove that this scheme is at least as hard to break as normal RSA; that is, prove that if this scheme can be broken, normal RSA can be as well. We consider RSA to be broken if knowing pq allows you to deduce (p−1)(q−1). We consider squared RSA to be broken if knowing p2q2 allows you to deduce p(p−1)q(q−1).
                                                                                                                                                                               2

 

 

If f and g are non-zero real polynomials, how many roots do the following polynomials have at least? How many can they have at most? (Your answer may depend on the degrees of f and g.)f +g
f g
f/g, assuming that f/g is a polynomial
Now let f and g be polynomials over GF(p).If f g = 0, is it true that either f = 0 or g = 0?
If deg f ≥ p, show that there exists a polynomial h with degh < p such that f(x)= h(x) for all x ∈ {0,1,...,p−1}.
How many f of degree exactly d < p are there such that f(0)= a for some fixed a ∈ {0,1,...,p−1}?
Find a polynomial f over GF(5) that satisfies f(0)= 1, f(2)= 2, f(4)= How many such polynomials are there?
2         The CRT and Lagrange Interpolation
Let n1,...nk be pairwise coprime, i.e. ni and nj are coprime for all i 6= j. The Chinese Remainder Theorem (CRT) tells us that there exist solutions to the following system of congruences:

x ≡ a1 (mod n1)
(1)
x ≡ a2 (mod n2)
(2)
...
.

(..)
x ≡ ak (mod nk)
(k)
and all solutions are equivalent (mod n1n2 ···nk). For this problem, parts (a)-(c) will walk us through a proof of the Chinese Remainder Theorem. We will then use the CRT to revisit Lagrange interpolation.

We start by proving the k = 2 case: Prove that we can always find an integer x1 that solves (1) and (2) with a1 = 1,a2 = Similarly, prove that we can always find an integer x2 that solves (1) and (2) with a1 = 0,a2 = 1.
Use part (a) to prove that we can always find at least one solution to (1) and (2) for any a1,a2. Furthermore, prove that all possible solutions are equivalent (mod n1n2).
Now we can tackle the case of arbitrary k: Use part (b) to prove that there exists a solution x to (1)-(k) and that this solution is unique (mod n1n2 ··nk).
For two polynomials p(x) and q(x), mimic the definition of a mod b for integers to define p(x) mod q(x). Use your definition to find p(x) mod (x−1).
Define the polynomials x−a and x−b to be coprime if they have no common divisor of degree 1. Assuming that the CRT still holds when replacing x,ai and ni with polynomials (using the definition of coprime polynomials just given), show that the system of congruences
p(x) ≡ y1 (mod (x−x1))   (1’) p(x) ≡ y2 (mod (x−x2))    (2’)

                                                                                  ...                                                                (...)

                                                                               p(x) ≡ yk (mod (x−xk))                                          (k’)

has a unique solution (mod (x−x1)···(x−xk)) whenever the xi are pairwise distinct. What is the connection to Lagrange interpolation?

3      Old secrets, new secrets
In order to share a secret number s, Alice distributed the values (1,p(1)),(2,p(2)),...,(n+1,p(n+1)) of a degree n polynomial p with her friends Bob1,...,Bobn+1. As usual, she chose p such that p(0)= s. Bob1 through Bobn+1 now gather to jointly discover the secret. Suppose that for some reason Bob1 already knows s, and wants to play a joke on Bob2,...,Bobn+1, making them believe that the secret is in fact some fixed s0 6= s. How can he achieve this?

4        Berlekamp-Welch for General Errors
Suppose that Hector wants to send you a length n = 3 message, m0,m1,m2, with the possibility for k = 1 error. For all parts of this problem, we will work mod 11, so we can encode 11 letters as shown below:

A
B
C
D
E
F
G
H
I
J
K
0
1
2
3
4
5
6
7
8
9
10
Hector encodes the message by finding the degree ≤ 2 polynomial P(x) that passes through (0,m0), (1,m1), and (2,m2), and then sends you the five packets P(0),P(1),P(2),P(3),P(4) over a noisy channel. The message you receive is

DHACK ⇒ 3,7,0,2,10 = r0,r1,r2,r3,r4

which could have up to 1 error.

First, let’s locate the error, using an error-locating polynomial E(x). Let Q(x) = P(x)E(x).
Recall that

                                                          Q(i)= P(i)E(i)= riE(i),          for      0 ≤ i < n+2k.

What is the degree of E(x)? What is the degree of Q(x)? Using the relation above, write out the form of E(x) and Q(x) in terms of the unknown coefficients, and then a system of equations to find both these polynomials.

Solve for Q(x) and E(x). Where is the error located?
Finally, what is P(x)? Use P(x) to determine the original message that Hector wanted to send.
5       Error-Detecting Codes
Suppose Alice wants to transmit a message of n symbols, so that Bob is able to detect rather than correct any errors that have occured on the way. That is, Alice wants to find an encoding so that

Bob, upon receiving the code, is able to either

tell that there are no errors and decode the message, or
realize that the transmitted code contains at least one error, and throw away the message.
Assuming that we are guaranteed a maximum of k errors, how should Alice extend her message (i.e. by how many symbols should she extend the message, and how should she choose these symbols)? You may assume that we work in GF(p) for very large prime p. Show that your scheme works, and that adding any lesser number of symbols is not good enough.

 

 

1      Bijective or not?

Decide whether the following functions are bijections or not. Please prove your claims.

f(x)= 10 5xfor domain R and range R
for domain Z[{p} and range R
f(x)= p mod x, where p 2 is a primefor domain N\{0} and range {0,...,p}
for domain {(p+1)/2,...,p} and range {0,...,(p 1)/2}
f(x)={x}, where the domain isD).D ={0,...,n} and the range is P(D), the powerset of D (that is, the set of all subsets of
Consider the number X = 1234567890, and obtain X0 by shuffling the order of the digits of X. Is f(i)=(i+1)st digit of X0 a bijection from {0,...,9} to itself?
2      Counting Tools

Are the following sets countable or uncountable? Please prove your claims.

A⇥B, where A and B are both countable.
Si2A Bi, where A,Bi are all countable.
The set of all functions f from N to N such that f is non-decreasing. That is, f(x) f(y) whenever x  y.
The set of all functions f from N to N such that f is non-increasing. That is, f(x) f(y) whenever x  y.
The set of all bijective functions from N to N.
3       Impossible Programs

Show whether the following programs can exist or not.

A program P that takes in any program F, input x and output y and returns true if F(x) outputs y and false otherwise.
A program P that takes in two programs F and G and returns true if F and G halt on the same inputs, and false otherwise.
4     Undecided?

Let us think of a computer as a machine which can be in any of n states {s1,...,sn}. The state of a 10 bit computer might for instance be specified by a bit string of length 10, making for a total of 210 states that this computer could be in at any given point in time. An algorithm A then is a list of k instructions (i0,i2,...,ik 1), where each il is a function of a state c that returns another state u and a number j. Executing A(x) means computing

                            (c1, j1)= i0(x),                  (c2, j2)= ij1(c1),                  (c3, j3)= ij2(c2),                 ...

until j`           k for some `, at which point the algorithm halts and returns c` 1.

How many iterations can an algorithm of k instructions perform on an n-state machine (at most) without repeating any computation?
Show that if the algorithm is still running after 2n2k2 iterations, it will loop forever.
Give an algorithm that decides whether an algorithm A halts on input x or not. Does your contruction contradict the undecidability of the halting problem?
5       Clothing Argument

There are four categories of clothings (shoes, trousers, shirts, hats) and we have ten distinct items in each category. How many distinct outfits are there if we wear one item of each category?
How many outfits are there if we wanted to wear exactly two categories?
How many ways do we have of hanging four of our ten hats in a row on the wall? (Order matters.)
We can pack four hats for travels. How many different possibilities for packing four hats are there? Can you express this number in terms of your answer to part (c)?
If we have exactly 3 red hats, 3 green hats and 4 turquoise hats, and hats of the same colour are indistinguishable, how many distinct sets of three hats can we pack?
 

 
1        Counting, Counting, and More Counting
The only way to learn counting is to practice, practice, practice, so here is your chance to do so. For this problem, you do not need to show work that justifies your answers. We encourage you to leave your answer as an expression (rather than trying to evaluate it to get a specific number).

How many ways are there to arrange n 1s and k 0s into a sequence?
A bridge hand is obtained by selecting 13 cards from a standard 52-card deck. The order of the cards in a bridge hand is irrelevant.
How many different 13-card bridge hands are there? How many different 13-card bridge hands are there that contain no aces? How many different 13-card bridge hands are there that contain all four aces? How many different 13-card bridge hands are there that contain exactly 6 spades?

Two identical decks of 52 cards are mixed together, yielding a stack of 104 cards. How many different ways are there to order this stack of 104 cards?
How many 99-bit strings are there that contain more ones than zeros?
An anagram of FLORIDA is any re-ordering of the letters of FLORIDA, i.e., any string made up of the letters F, L, O, R, I, D, and A, in any order. The anagram does not have to be an English word.
How many different anagrams of FLORIDA are there? How many different anagrams of ALASKA are there? How many different anagrams of ALABAMA are there? How many different anagrams of MONTANA are there?

How many different anagrams of ABCDEF are there if: (1) C is the left neighbor of E; (2) C is on the left of E (and not necessarily E’s neighbor)
We have 9 balls, numbered 1 through 9, and 27 bins. How many different ways are there to distribute these 9 balls among the 27 bins? Assume the bins are distinguishable (e.g., numbered 1 through 27).
We throw 9 identical balls into 7 bins. How many different ways are there to distribute these 9 balls among the 7 bins such that no bin is empty? Assume the bins are distinguishable (e.g., numbered 1 through 7).
How many different ways are there to throw 9 identical balls into 27 bins? Assume the bins are distinguishable (e.g., numbered 1 through 27).
There are exactly 20 students currently enrolled in a class. How many different ways are there to pair up the 20 students, so that each student is paired with one other student?
How many solutions does x0 +x1 +···+xk = n have, if each x must be a non-negative integer? (l) How many solutions does x0 +x1 = n have, if each x must be a strictly positive integer?
(m) How many solutions does x0 +x1 +···+xk = n have, if each x must be a strictly positive integer?

2      Binomial Beads
Alistair is making school spirit keychains, which consist of a sequence of n beads on a string. He has blue beads and gold beads. How many unique keychains can he make with exactly k ≤ n blue beads?
Alistair decides to sell his keychains! He decides on the following pricing scheme:Blue beads have a value of x
Gold beads have a value of y
The price of a keychain is the product of the values of all of its beads.
What is the price of a keychain with exactly k ≤ n blue beads?

Alistair decides to make exactly one of every possible unique keychain. If he sells every keychain he creates, how much revenue will he make? Use parts (a) and (b), and leave your answer in summation form.
Draw a connection between part (c) and the binomial theorem.
(x+y)n = xkyn−k

Hint: How do you calculate the product (x + y)(x + y)?

3     Minesweeper
Minesweeper is a game that takes place on a grid of squares. When you click a square, it disappears to reveal either an integer ∈ [1,8], a mine, or a blank space. If it reveals a mine, you instantly lose. If it reveals a number, that number refers to the number of mines adjacent to that square (including diagonally adjacent). If it reveals a blank space, there were 0 mines adjacent to it.

You are playing on a 8x8 board with 10 mines randomly distributed across the board. In your first move, you click a square near the center of the board.

What is the probability that the square reveals...a mine?
a blank space?
the number k?
The first square you picked revealed the number k. For your next move, you want to minimize the probability of picking a mine. Should you pick a square adjacent to your first pick, or a different square? Your answer should depend on the value of k.
Your first move resulted in the number 1. You pick the square to the right for your next move.
What is the probability that this square reveals the number 4?

4       Playing Strategically
Bob, Eve and Carol bought new slingshots. Bob is not very accurate hitting his target with probability 1/3. Eve is better, hitting her target with probability 2/3. Carol never misses. They decide to play the following game: They take turns shooting each other. For the game to be fair, Bob starts first, then Eve and finally Carol. Any player who gets shot has to leave the game. The last person standing wins the game. What is Bob’s best course of action regarding his first shot?

Compute the probability of the event E1 that Bob wins in a duel against Eve alone, assuming he shoots first.
Compute the probability of the event E2 that Bob wins in a duel against Eve alone, assuming he shoots second.
Compute the probability of the same events for a duel of Bob against Carol.
Assuming that both Eve and Carol play rationally, conclude that Bob’s best course of action is to shoot into the air (i.e., intentionally miss)! (Hint: What happens if Bob misses? What if he doesn’t?)
5     Weathermen
Tom is a weatherman in New York. On days when it snows, Tom correctly predicts the snow 70% of the time. When it doesn’t snow, he correctly predicts no snow 95% of the time. In New York, it snows on 10% of all days.

If Tom says that it is going to snow, what is the probability it will actually snow?
What is Tom’s overall accuracy?
Tom’s friend Jerry is a weatherman in Alaska. Jerry claims that she is a better weatherman than Tom even though her overall accuracy is lower. After looking at their records, you determine that Jerry is indeed better than Tom at predicting snow on snowy days and sun on sunny days. How is this possible?
Hint: what is the weather like in Alaska?

 

 

(i) Let X ∼ Bin(5,1/4). Let Y be a random variable equal to 5−X. What are the distributions of X and Y?
(ii) Let Z be a random variable denoting the result of a die roll (so 1 ≤ Z ≤ 6 uniformly at random). What is E[Z2]?

For each of the problems below, if you think the answer is "yes" then provide a proof. If you think the answer is "no", then provide a counterexample.

If A and B are integer-valued random variables such that for every integer i, P(A = i) = P(B =
i), then is P(A = B) 0?

If C is an integer-valued random variable, then is E[C2] = E[C]2?
If X and Y are random variables and E[X] 100E[Y], then is P(X Y) 1/100?
If X and Y are random variables taking positive values, then isY]?
If A,B,C are events such that P(A∩B∩C) = P(A)P(B)P(C), then are A,B,C mutually independent?
Is an event A never independent with itself?
If A and B are independent events, then are A and B independent?
2       Airport Revisited
Suppose that there are n airports arranged in a circle. A plane departs from each airport, and randomly chooses an airport to its left or right to fly to. What is the expected number of empty airports after all planes have landed?
Now suppose that we still have n airports, but instead of being arranged in a circle, they form a general graph, where each airport is denoted by a vertex, and an edge between two airports indicates that a flight is permitted between them. There is a plane departing from each airport and randomly chooses a neighboring destination where a flight is permitted. What is the expected number of empty airports after all planes have landed? (Express your answer in terms of N(i) - the set of neighboring airports of airport i, and deg(i) - the number of neighboring airports of airport i).
3      Fizzbuzz
Fizzbuzz is a classic software engineering interview question. You are given a natural number n, and for each integer i from 1 to n you have to print either "fizzbuzz" if i is divisible by 15, "fizz" if i is divisible by 3 but not 15, "buzz" if i is divisible by 5 but not 15, or the integer itself if i is not divisible by 3 or 5.
If n is a multiple of 15, then how many printed lines will contain an integer?

(Hint: If you pick a line uniformly at random, then what is the probability that the printed line contains an integer?)

Recall the Euler totient function from Homework 4:
φ(n) = |{i : 1 ≤ i ≤ n,gcd(i,n) = 1}|.

Suppose n = pα11pα22 ···pαkk where p1,p2,...,pk are distinct primes and α1,α2,...,αk are positive integers. Prove that

φ(n)

                                                                              n = ∏j

4        Cliques in Random Graphs
Consider a graph G = (V,E) on n vertices which is generated by the following random process: for each pair of vertices u and v, we flip a fair coin and place an (undirected) edge between u and v if and only if the coin comes up heads. So for example if n = 2, then with probability 1/2, G = (V,E) is the graph consisting of two vertices connected by an edge, and with probability 1/2 it is the graph consisting of two isolated vertices.

What is the size of the sample space?
A k-clique in graph is a set of k vertices which are pairwise adjacent (every pair of vertices is connected by an edge). For example a 3-clique is a triangle. What is the probability that a particular set of k vertices forms a k-clique?
Prove that nk.
Optional: Can you come up with a combinatorial proof? Of course, an algebraic proof would also get full credit.

Prove that the probability that the graph contains a k-clique, for k ≥ 4logn+1, is at most 1/n. (The log is taken base 2).
Hint: Apply the union bound and part (c).

5          Balls and Bins, All Day Every Day
You throw n balls into n bins uniformly at random, where n is a positive even integer.

What is the probability that exactly k balls land in the first bin, where k is an integer 0 ≤ k ≤ n?
What is the probability p that at least half of the balls land in the first bin? (You may leave your answer as a summation.)
Using the union bound, give a simple upper bound, in terms of p, on the probability that some bin contains at least half of the balls.
What is the probability, in terms of p, that at least half of the balls land in the first bin, or at least half of the balls land in the second bin?
After you throw the balls into the bins, you walk over to the bin which contains the first ball you threw, and you randomly pick a ball from this bin. What is the probability that you pick up the first ball you threw? (Again, leave your answer as a summation.)
 

 

Mr. and Mrs. Brown decide to continue having children until they either have their first girl or until they have three children. Assume that each child is equally likely to be a boy or a girl, independent of all other children, and that there are no multiple births. Let G denote the numbers of girls that the Browns have. Let C be the total number of children they have.

Determine the sample space, along with the probability of each sample point.
Compute the joint distribution of G and C. Fill in the table below.
 
C=1
C=2
C=3
G=0
 
 
 
G=1
 
 
 
Use the joint distribution to compute the marginal distributions of G and C and confirm that the values are as you’d expect. Fill in the tables below.
 

P(G=0)
 
P(G=1)
 
 

P(C=1)
P(C=2)
P(C=3)
 
 
 
Are G and C independent?
What is the expected number of girls the Browns will have? What is the expected number of children that the Browns will have?
                                                                                                                                                                               1

2        Will I Get My Package?

A delivery guy in some company is out delivering n packages to n customers, where n∈N, n 1. Not only does he hand a random package to each customer, he opens the package before delivering it with probability 1/2. Let X be the number of customers who receive their own packages unopened.

Compute the expectation E(X).
Compute the variance var(X).
3         Double-Check Your Intuition Again

You roll a fair six-sided die and record the result X. You roll the die again and record the result Y.What is cov(X+Y,X−Y)?
Prove that X+Y and X−Y are not independent.
For each of the problems below, if you think the answer is "yes" then provide a proof. If you think the answer is "no", then provide a counterexample.

If X is a random variable and var(X)= 0, then must X be a constant?
If X is a random variable and c is a constant, then is var(cX)=cvar(X)?
If A and B are random variables with nonzero standard deviations and Corr(A,B)= 0, then are A and B independent?
If X and Y are not necessarily independent random variables, but Corr(X,Y)= 0, and X and Y have nonzero standard deviations, then is var(X+Y)= var(X)+var(Y)?
If X and Y are random variables then is E(max(X,Y)min(X,Y))=E(XY)?
If X and Y are independent random variables with nonzero standard deviations, then is
Corr(max(X,Y),min(X,Y))= Corr(X,Y)?

 
Cuckoo birds are parasitic beasts. They are known for hijacking the nests of other bird species and evicting the eggs already inside. Cuckoo hashing is inspired by this behavior. In cuckoo hashing, when we get a collision, the element that was already there gets evicted and rehashed.

We study a simple (but ineffective, as we’ll see) version of cuckoo hashing, where all hashes are random. Let’s say we want to hash n pieces of data D1,D2,...,Dn into n possible hash buckets labeled 1,...,n. We hash the D1,...,Dn in that order. When hashing Di, we assign it a random bucket chosen uniformly from 1,...,n. If there is no collision, then we place Di into that bucket. If there is a collision with some other Dj, we evict Dj and assign it another random bucket uniformly from 1,...,n. (It is possible that Dj gets assigned back to the bucket it was just evicted from!) We again perform the eviction step if we get another collision. We keep doing this until there is no more collision, and we then introduce the next piece of data, Di+1 to the hash table.

What is the probability that there are no collisions over the entire process of hashing D1,...,Dn to buckets 1,...,n? What value does the probability tend towards as n grows very large?
Assume we have already hashed D1,...,Dn−1, and they each occupy their own bucket. We now introduce Dn into our hash table. What is the expected number of collisions that we’ll see while hashing Dn? (Hint: What happens when we hash Dn and get a collision, so we evict some other Di and have to hash Di? Are we at a situation that we’ve seen before?)
2         Markov’s Inequality and Chebyshev’s Inequality
A random variable X has variance var(X) = 9 and expectation E[X] = 2. Furthermore, the value of X is never greater than 10. Given this information, provide either a proof or a counterexample for the following statements.

P[X ≤ 1] ≤ 8/
P[X ≥ 6] ≤ 9/
P[X ≥ 6] ≤ 9/
3      Easy A’s
A friend tells you about a course called “Laziness in Modern Society” that requires almost no work. You hope to take this course next semester to give yourself a well-deserved break after working hard in CS 70. At the first lecture, the professor announces that grades will depend only on two homework assignments. Homework 1 will consist of three questions, each worth 10 points, and Homework 2 will consist of four questions, also each worth 10 points. He will give an A to any student who gets at least 60 of the possible 70 points.

However, speaking with the professor in office hours you hear some very disturbing news. He tells you that, in the spirit of the class, the GSIs are very lazy, and to save time the grading will be done as follows. For each student’s Homework 1, the GSIs will choose an integer randomly from a distribution with mean µ = 5 and variance σ2 = 1. They’ll mark each of the three questions with that score. To grade Homework 2, they’ll again choose a random number from the same distribution, independently of the first number, and will mark all four questions with that score.

If you take the class, what will the mean and variance of your total class score be? Use Chebyshev’s inequality to conclude that you have less than a 5% chance of getting an A when the grades are randomly chosen this way.

4       Confidence Interval Introduction
We observe a random variable X which has mean µ and standard deviation σ ∈ (0,∞). Assume that the mean µ is unknown, but σ is known.

We would like to give a 95% confidence interval for the unknown mean µ. In other words, we want to give a random interval (a,b) (it is random because it depends on the random observation X) such that the probability that µ lies in (a,b) is at least 95%.

We will use a confidence interval of the form (X −ε,X +ε), where ε 0 is the width of the confidence interval. When ε is smaller, it means that the confidence interval is narrower, i.e., we are giving a more precise estimate of µ.

Using Chebyshev’s Inequality, calculate an upper bound on P{|X −µ| ≥ ε}.
Explain why P{|X −µ| < ε} is the same as P{µ ∈ (X −ε,X +ε)}.
Using the previous two parts, choose the width of the confidence interval ε to be large enough so that P{µ ∈ (X −ε,X +ε)} is guaranteed to exceed 95%.
[Note: Your confidence interval is allowed to depend on X, which is observed, and σ, which is known. Your confidence interval is not allowed to depend on µ, which is unknown.]

The previous three parts dealt with the case when you observe one sample X. Now, let n be a positive integer and let X1,...,Xn be i.i.d. samples, each with mean µ and standard deviation σ ∈ (0,∞). As before, assume that µ is unknown but σ is known.
Here, a good estimator for µ is the sample mean X¯ := n−1 ∑ni=1 Xi. Calculate the mean and variance of X¯.

We will now use a confidence interval of the form (X¯ −ε,X¯ +ε) where ε 0 again represents the width of the confidence interval. Imitate the steps of (a) through (c) to choose the width ε to be large enough so that P{µ ∈ (X¯ −ε,X¯ +ε)} is guaranteed to exceed 95%.
To check your answer, your confidence interval should be smaller when n is larger. Intuitively, if you collect more samples, then you should be able to give a more precise estimate of µ.

 

 
 

It’s that time of the year again - Safeway is offering its Monopoly Card promotion. Each time you visit Safeway, you are given one of n different Monopoly Cards with equal probability. You need to collect them all to redeem the grand prize.

Let X be the number of visits you have to make before you can redeem the grand prize. Show that

 [Hint: Does this remind you of a particular problem? What is the

expectation for this problem?]

2       Geometric Distribution
Two faulty machines, M1 and M2, are repeatedly run synchronously in parallel (i.e., both machines execute one run, then both execute a second run, and so on). On each run, M1 fails with probability p1 and M2 fails with probability p2, all failure events being independent. Let the random variables X1, X2 denote the number of runs until the first failure of M1, M2 respectively; thus X1, X2 have geometric distributions with parameters p1, p2 respectively. Let X denote the number of runs until the first failure of either machine.

Show that X also has a geometric distribution, with parameter p1 + p2 − p1p2.
Now, two technicians are hired to check on the machines every run. They decide to take turns checking on the machines every hour. What is the probability that the first technician is the first one to find a faulty machine?
                                                                                                                                                                                 1

3      Geometric and Poisson
Let X be geometric with parameter p,Y be Poisson with parameter λ, and Z = max(X,Y). Assume X and Y are independent. For each of the following parts, your final answers should not have summations.

(a) Compute P(X Y). (b) Compute P(Z ≥ X).

(c) Compute P(Z ≤Y).

4      Darts
Alvin is playing darts. His aim follows an exponential distribution; that is, the probability density that the dart is x distance from the center is fX(x) = exp(−x). The board’s radius is 4 units.

What is the probability the dart will stay within the board?
Say you know Alvin made it on the board. What is the probability he is within 1 unit from the center?
If Alvin is within 1 unit from the center, he scores 4 points, if he is within 2 units, he scores 3, etc. In other words, Alvin scores b5−xc, where x is the distance from the center. What is Alvin’s expected score after one throw?
5       Exponential Practice
Let X1,X2 ∼ Exponential(λ) be independent, λ  Calculate the density of Y := X1 +X2. [Hint: One way to approach this problem would be to compute the CDF of Y and then differentiate the CDF.]
Let t  What is the density of X1, conditioned on X1 +X2 = t? [Hint: Once again, it may be helpful to consider the CDF P(X1 ≤ x | X1 +X2 = t). To tackle the conditioning part, try conditioning instead on the event {X1 +X2 ∈ [t,t +ε]}, where ε 0 is small.]
6      Uniform Means
Let X1,X2,...,Xn be n independent and identically distributed uniform random variables on the interval [0,1] (where n is a positive integer).

Let Y = min{X1,X2,...,Xn}. Find E(Y). [Hint: Use the tail sum formula, which says the expected value of a nonnegative random variable isdx. Note that we can use the tail sum formula since Y ≥ ]
Let Z = max{X1,X2,...,Xn}. Find E(Z). [Hint: Find the CDF.]
CS 70, Fall 2018, HW 12                                                                                                                                                                                     2

 

CS 70 Discrete Mathematics and Probability Theory Fall 2018 Course Notes HW13
Due: Friday, November 30, 2018 at 10PM

Sundry
Before you start your homework, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)

In this problem, we will consider Buffon’s Needle, but with a catch. We now drop a needle at random onto a large grid, and example of which is shown below.

The length of the needle is 1, and the space between the grid lines is 1 as well.

Recall from class that a random throw means that the position of the center of the needle and its orientation are independent and uniformly distributed.

Given that the angle between the needle and the horizontal lines is θ, what is the probability that the needle does not intersect any grid lines? Justify your answer.
Continue part (a) to find the probability that the needle, when dropped onto the grid at random (with the angle chosen uniformly at random), intersects a grid line. Justify your answer.
Hint: You may use the fact that sinθ cosθ =  sin(2θ) without proof.

Let X be the number of times the needle intersects a gridline (so, in the example shown above, X = 2). Find E[X]. Justify your answer.
Hint: Can you do this without using your answer from part (b)?

Combine the previous parts to figure out the probability that X = 1, i.e. the needle will only intersects one gridline. Justify your answer.
We will fold the needle into an equilateral triangle, where each side is length . What is the expected number of intersections that this triangle will have with the gridlines, when dropped onto the grid? Justify your answer.
2         Variance of the Minimum of Uniform Random Variables
i.i.d.

Let n be a positive integer and let X1,...,Xn ∼ Uniform[0,1]. Find varY, where

Y := min{X1,...,Xn}.

Hint: You may need to perform integration by parts.

3        Erasures, Bounds, and Probabilities
Alice is sending 1000 bits to Bob. The probability that a bit gets erased is p, and the erasure of each bit is independent of the others.

Alice is using a scheme that can tolerate up to one-fifth of the bits being erased. That is, as long as Bob receives at least 801 of the 1000 bits correctly, he can decode Alice’s message.

In other words, Bob becomes unable to decode Alice’s message only if 200 or more bits are erased. We call this a “communication breakdown”, and we want the probability of a communication breakdown to be at most 10−6.

Use Markov’s inequality to upper bound p such that the probability of a communications breakdown is at most 10−6.
Use Chebyshev’s inequality to upper bound p such that the probability of a communications breakdown is at most 10−6.
As the CLT would suggest, approximate the fraction of erasures by a Gaussian random variable (with suitable mean and variance). Use this to find an approximate bound for p such that the probability of a communications breakdown is at most 10−6.
4         Sampling a Gaussian With Uniform
In this question, we will see one way to generate a normal random variable if we have access to a random number generator that outputs numbers between 0 and 1 uniformly at random.

As a general comment, remember that showing two random variables have the same CDF or PDF is sufficient for showing that they have the same distribution.

First, let us see how to generate an exponential random variable with a uniform random variable. Let U1 ∼Uniform(0,1). Prove that −lnU1 ∼ Expo(1).
Let N1,N2 ∼ N (0,1), where N1 and N2 are independent. Prove that N.
Hint: You may use the fact that over a region R, if we convert to polar coordinates (x,y) → (r,θ), then the double integral over the region R will be

ZZ    ZZ f(x,y)dxdy =              f(rcosθ,rsinθ)·rdrdθ.

                                                          R                                                R

Suppose we have two uniform random variables, U1 and U2. How would you transform these two random variables into a normal random variable with mean 0 and variance 1?
Hint: What part (b) tells us is that the point (N1,N2) will have a distance from the origin that is distributed as the square root of an exponential distribution. Try to useU1 to sample the radius, and then use U2 to sample the angle.

5       Markov Chain Terminology
In this question, we will walk you through terms related to Markov chains.

(Irreducibility) A Markov chain is irreducible if, starting from any state i, the chain can transition to any other state j, possibly in multiple steps.
(Periodicity) d(i) := gcd{n 0 |Pn(i,i)=P[Xn =i|X0 =i] 0}, i∈X . If d(i)= 1 ∀i∈X , then the Markov chain is aperiodic; otherwise it is periodic.
(Matrix Representation) Define the transition probability matrix P by filling entry (i, j) with probability P(i, j).
(Invariance) A distribution π is invariant for the transition probability matrix P if it satisfies the following balance equations: π = πP.
a

1−b1−a

b

For what values of a and b is the above Markov chain irreducible? Reducible?
For a = 1, b = 1, prove that the above Markov chain is periodic.
For 0 < a < 1, 0 < b < 1, prove that the above Markov chain is aperiodic.
Construct a transition probability matrix using the above Markov chain.
Write down the balance equations for this Markov chain and solve them. Assume that the Markov chain is irreducible.
6       Analyze a Markov Chain
Consider the Markov chain X(n) with the state diagram shown below where a,b ∈ (0,1).

                                                                                               a                b

1 - a 

                                                                                     0   1 - b     1      1      2

Show that this Markov chain is aperiodic;
Calculate P[X(1) = 1,X(2) = 0,X(3) = 0,X(4) = 1 | X(0) = 0];
Calculate the invariant distribution;
Let Ti = min{n ≥ 0 | X(n) = i}, Ti is the number of steps until we transit to state i for the first time. Calculate E[T2 | X(0) = 1].
7       Boba in a Straw
Imagine that Jonathan is drinking milk tea and he has a very short straw: it has enough room to fit two boba (see figure).

 
 
Figure 1: A straw with one boba currently inside. The straw only has enough room to fit two boba.

Here is a formal description of the drinking process: We model the straw as having two “components” (the top component and the bottom component). At any given time, a component can contain nothing, or one boba. As Jonathan drinks from the straw, the following happens every second:

The contents of the top component enter Jonathan’s mouth.
The contents of the bottom component move to the top component.
With probability p, a new boba enters the bottom component; otherwise the bottom component is now empty.
Help Jonathan evaluate the consequences of his incessant drinking!

At the very start, the straw starts off completely empty. What is the expected number of seconds that elapse before the straw is completely filled with boba for the first time? [Write down the equations; you do not have to solve them.]
Consider a slight variant of the previous part: now the straw is narrower at the bottom than at the top. This affects the drinking speed: if either (i) a new boba is about to enter the bottom component or (ii) a boba from the bottom component is about to move to the top component, then the action takes two seconds. If both (i) and (ii) are about to happen, then the action takes three seconds. Otherwise, the action takes one second. Under these conditions, answer the previous part again. [Write down the equations; you do not have to solve them.]
Jonathan was annoyed by the straw so he bought a fresh new straw (the straw is no longer narrow at the bottom). What is the long-run average rate of Jonathan’s calorie consumption? (Each boba is roughly 10 calories.)
What is the long-run average number of boba which can be found inside the straw? [Maybe you should first think about the long-run distribution of the number of boba.]