Problem Set 10 Solutions Due: Monday, May 2 at 9 PM Problem 1. Justify your answers to the following questions about independence. (a)Suppose that you roll a fair die that has six sides, numbered 1, 2, ... 6. Is the event that the number on top is a multiple of independent of the event that the number on top is a multiple of 3?

Problem Set 9 Solutions Due: Monday, April 25 at 9 PM Problem 1. There are three coins: a penny, nickel, and a quarter. When these coins are flipped: The penny comes up heads with probability 1/3 and tails with probability 2/3 The nickel comes up heads with probability 3/4 and tails with probability 1/4. The quarter comes up heads with

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

Due: Monday, April 11 at 9 PM Problem 1. An electronic toy displays a 4x4 grid of colored squares. At all times, four are red, four are green, four are blue, and four are yellow. For example, here is one possible configuration:

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 1. An undirected graph G has width w if the vertices can be arranged in a se- quence V1,2,3,…,Vn such that each vertex v; is joined by an edge to at most w preceding vertices. (Vertex vj precedes if i.) Use induction to prove that every graph with width at most w is (w+1)-colorable

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 3 Solutions Due: Tuesday, February 22 at 9 PM Problem 1. An urn contains 75 white balls and 150 black balls. while there are at least 2 balls remaining in the urn, you repeat the following operation. You remove 2 balls elected arbitrarily and then: If at least one of the two balls is black, then you discard one black ball and put the other ball back in the urn

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

Problem set 1 Solutions Due: Monday February 7 at 9 PM Problem 1. The connectives A(and), V(or), and =(implies)come often not only in com uter programs, but also everyday speech. But devices that compute the nand operation