Srini Devadas and Eric Lehman Problem Set 7 Solutions Due: Monday, April 4 at 9 PM Problem 1. Every function has some subset of these properties: injective

Problem 1. Sammy the Shark is a financial service provider who offers loans on the fol lowing terms. Sammy loans a client m dollars in the morning This puts the client m dollars in debt to Sammy. Each evening, Sammy first charges\service fee\, which increases the client's debt by f dollars, and then Sammy charges interest, which multiplies the debt by a factor

Problem Set 4 Solutions Due: Monday, February 28 at 9 PM Problem 1. Prove all of the following statements except for the two that are false; for those, provide counterexamples. Assumen 1. When proving each statement, you may assume all its predecessors (a)a =(mod n) Solution. Every number divides zero, so n (a-a), which means a a (mod n). (b)a≡b(modn) impliesa(modn)

Problem set 2 Solutions Due: Monday, February 14 at 9 PM Problem 1. Use induction to prove that n/n for alln olution. The proof is by induction on n. Let P(n) be the proposition that the equation Base case. P(2 )is true because Inductive step. Assume P(n)is true. Then we can prove P(n +1)is also true as follows

1 Stencil the flea There is a small flea named Stencil. To his right, there is an endless flat plateau. One inch to his left is the Cliff of Doom, which drops to a raging sea filled with flea-eating monsters Cliff of doom

Problem 1. A couple decides to have children until they have both a boy and a girl. What is the expected number of children that they'll end up with? Assume that each child is equally likely to be a boy or a girl and genders are mutually independent Solution. There are many ways to solve

Problem 1. Suppose that you flip three fair mutually independent coins. Define the fol- lowing events: Let be the event that the first coin is heads. · Let be the event that the second coin is heads. · Let be the event that the third coin is heads

This is a good approach to questions of the form, What is the probability that ntuition will mislead you, but this formal approach gives the right answer every time 1. Find the sample space. ( Use a tree diagram. 2. Define events of interest. Mark leaves corresponding to these events 3. Determine outcome probabilities (a) Assign edge probabilities

Notes for Recitation 14 Counting Rules Rule 1(Generalized Product Rule). Let be a set of length-k sequences. If there are: n1 possible first entries, n2 possible second entries for each first entry, n3 possible third entries for each combination of first and second entries, etc. then:

Notes for Recitation 13 Basic Counting Notions bijection or bijective function is function:x→ such that every element of the codomain is related to exactly one element of the domain. Here is an example of a bijection: