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

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

1 Conditional Expectation and Total Expectation There are conditional expectations, just as there are conditional probabilities. If R is a random variable and e is an event, then the conditional expectation Ex(r e)is defined