6.042/18.] Mathematics for Computer Science March 9. 2005 Srini devadas and Eric Lehman Quiz 1 YOUR NAME Circle the name of your recitation instructor Ishan Christos Grant You may use one 8.5 11"sheet with notes in you own handwriting on both sides but no other sources of information Calculators are not allowed You may assume all results from lecture, the notes, problem sets, and recitation Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them The exam ends at 9: 30 PM · GOOD LUCK! Problem Points Grade Grader 20 123456 15 20 15 15 15 匚 Total100
6.042/18.062J Mathematics for Computer Science March 9, 2005 Srini Devadas and Eric Lehman Quiz 1 YOUR NAME: Circle the name of your recitation instructor: Ishan Christos Grant • You may use one 8.5 × 11” sheet with notes in you own handwriting on both sides, but no other sources of information. • Calculators are not allowed. • You may assume all results from lecture, the notes, problem sets, and recitation. • Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. • Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them. • The exam ends at 9:30 PM. • GOOD LUCK! Problem Points Grade Grader 1 20 2 15 3 20 4 15 5 15 6 15 Total 100
Problem 1.20 point (a)Consider the proposition: R=“ For all x∈S,P(x) implies Q(x) For each statement below: · If r implies that statement, then circle→. If R is implied by that statement, then circle Thus, you might circle zero, one or two arrows next to each statement. Circle only implications that hold for all sets S and all predicates P and Q) For all c E s, Q(ar) implies P(a) For all x E S, - Q()implies P(a) or all T E S, P(r)and Q(a) There does not exist an E S such that not(P(ar) implies Q(a)) fl
Quiz 1 2 Problem 1. [20 points] (a) Consider the proposition: R = “For all x ∈ S, P(x) implies Q(x).” For each statement below: • If R implies that statement, then circle ⇒. • If R is implied by that statement, then circle ⇐. Thus, you might circle zero, one, or two arrows next to each statement. (Circle only implications that hold for all sets S and all predicates P and Q.) ⇒ ⇐ For all x ∈ S, Q(x) implies P(x). ⇒ ⇐ For all x ∈ S, ¬Q(x) implies ¬P(x). ⇒ ⇐ For all x ∈ S, P(x) and Q(x). ⇒ ⇐ There does not exist an x ∈ S such that not (P(x) implies Q(x)). ⇒ ⇐ Pigs fly
(b) Let S be the set of all people, and let M(a, y) be the predicate, r is the mother of y". Translate this proposition into a clear English sentence involving no variables vx(=y(M(x,y)∧M(y,x) There are no two people such that each is the mother of the other. "Or more simply, "No one is their own maternal grandmother (c) Translate the following English sentence into logic notation using the set S and redicatem defined above Everyone has a mother. vx彐yM(y,x)
Quiz 1 3 (b) Let S be the set of all people, and let M(x, y) be the predicate, “x is the mother of y”. Translate this proposition into a clear English sentence involving no variables. ∀x (¬∃y (M(x, y) ∧ M(y, x))) “There are no two people such that each is the mother of the other.” Or, more simply, “No one is their own maternal grandmother.” (c) Translate the following English sentence into logic notation using the set S and predicate M defined above. “Everyone has a mother.” ∀x ∃y M(y, x)
Problem 2.[15 points] Complete this proof that n cents of postage can be formed using 3 and 5 cent stamps for all n 28 Proof. We use strong induction. (a)Let P(n)be the proposition that Solution. n cents of postage can be formed using 3 and 5 cent stamps (b) Base cases Solution. P(8), P(9), and P(10)are all true, since 9=3+3+3 (c) Inductive step Solution For n 10, we assume P( 8),..., P(n)and prove P(n+1). In particular, y assumption P(n-2), we can form n-2 cents of postage. Adding a 3-cent stamp gives n+1 cents of postage, so P(n+1) is true o P(n)is true for all n>8 by the principle of strong induction
Quiz 1 4 Problem 2. [15 points] Complete this proof that n cents of postage can be formed using 3 and 5 cent stamps for all n ≥ 8. Proof. We use strong induction. (a) Let P(n) be the proposition that Solution. n cents of postage can be formed using 3 and 5 cent stamps. (b) Base cases. Solution. P(8), P(9), and P(10) are all true, since: 8 = 5 + 3 9 = 3 + 3 + 3 10 = 5 + 5 (c) Inductive step. Solution. For n ≥ 10, we assume P(8), . . . , P(n) and prove P(n + 1). In particular, by assumption P(n − 2), we can form n − 2 cents of postage. Adding a 3-cent stamp gives n + 1 cents of postage, so P(n + 1) is true. So P(n) is true for all n ≥ 8 by the principle of strong induction
Problem 3. [20 points] Here is how to tweak an undirected grap 1. Select distinct vertices a, b, c, and d such that the graph contains edges a-b and c-d and none of the edges a-c, a-d, b-c, or b- 2. Delete edge c-d and add edges a-c and a-d ●C (a) In the box on the right, draw a graph that can be obtained by tweaking the graph on the left 6 2 2 3 4
Quiz 1 5 Problem 3. [20 points] Here is how to tweak an undirected graph: 1. Select distinct vertices a, b, c, and d such that the graph contains edges a—b and c—d and none of the edges a—c, a—d, b—c, or b—d. ✇ ✇ ✇ a ✇ b c d 2. Delete edge c—d and add edges a—c and a—d: ❅ ❅ ❅ ❅ ❅ ❅ ✇ ❅❅ ✇ ✇ a ✇ b c d (a) In the box on the right, draw a graph that can be obtained by tweaking the graph on the left. ❍❍ ❍ ❍❍ ❍❍ ✟✟✟ ✟✟✟✟ ✟✟ ✟ ✟✟ ✟✟ ❍❍❍❍❍❍❍ ✇ ✇ ✇ ✇ ✇ ✇ 1 2 3 4 5 6 → ❍❍❍❍❍❍❍❍❍❍❍❍❍ ❍❍ ❍ ❍❍ ❍❍ ✟✟✟ ✟✟✟✟ ✟✟ ✟ ✟✟ ✟✟ ❍❍❍❍❍❍❍ ✇ ✇ ✇ ✇ ✇ ✇ 1 2 3 4 5 6
(b) Suppose that Go is an undirected graph with an Euler tour. Also, suppose G1 is obtained by tweaking Go, G2 by tweaking GI, and so forth. Use induction to prove that every graph Gn obtainable in this way has an Euler tour For your reference An Euler tour is a closed walk that traverses every edge in a graph exactly once A graph is connected if and only if there is a path between every pair of vertices Theorem. An undirected graph has an Euler tour if and only if the graph is connected and every vertex has even degree Solution. We use induction. Let P(n)be the proposition that Gn has an Euler tour Base case. Go has an Euler tour by supposition Inductive step. For n>0, we assume Gn has an Euler Tour and prove that gn+l also has an Euler tour. Specifically, we show that Gn+1 has only even-degree vertices and is connected Every vertex in Gn has even degree, since Gn has an Euler tour. Every vertex Thus, every vertex in Gn+1 has even degree Consider arbitrary vertices u and v in Gn+1. Since Gn is connected there is a path from u to u in Gn. If the path does not contain c-d, then the same path exists in Gn+1. If the path does contain c-d, then there is a corresponding path in Gn+1 where c-d is replaced by edges c-a and a-d This implies Gn+I has an Euler tour as well. Therefore gn has an euler tour for all n> 1. In particular, G6042 has an Euler Tour
Quiz 1 6 (b) Suppose that G0 is an undirected graph with an Euler tour. Also, suppose G1 is obtained by tweaking G0, G2 by tweaking G1, and so forth. Use induction to prove that every graph Gn obtainable in this way has an Euler tour. For your reference: • An Euler tour is a closed walk that traverses every edge in a graph exactly once. • A graph is connected if and only if there is a path between every pair of vertices. • Theorem. An undirected graph has an Euler tour if and only if the graph is connected and every vertex has even degree. Solution. We use induction. Let P(n) be the proposition that Gn has an Euler tour. Base case. G0 has an Euler tour by supposition. Inductive step. For n ≥ 0, we assume Gn has an Euler Tour and prove that Gn+1 also has an Euler tour. Specifically, we show that Gn+1 has only even-degree vertices and is connected: • Every vertex in Gn has even degree, since Gn has an Euler tour. Every vertex in Gn+1 has the same degree, except for vertex a which has degree two greater. Thus, every vertex in Gn+1 has even degree. • Consider arbitrary vertices u and v in Gn+1. Since Gn is connected, there is a path from u to v in Gn. If the path does not contain c—d, then the same path exists in Gn+1. If the path does contain c—d, then there is a corresponding path in Gn+1 where c—d is replaced by edges c—a and a—d. This implies Gn+1 has an Euler tour as well. Therefore, Gn has an Euler tour for all n ≥ 1. In particular, G6042 has an Euler Tour
Problem 4. [15 points] Fill in the boxes below. All variables denote integers. No exp nations are required, but we can only award partial credit for an incorrect answer if you show your reasoning (a) Suppose c is a multiple of 17. Write the smallest nonnegative integers that make this statement true 6x2+4x10-4x+6=0x+6(mod17) Solution. If r is a multiple of 17, then =0(mod 17). Therefore, all terms involving r on the left are congruent to zero (b)Now suppose a is not a multiple of 17. Write the smallest nonnegative integers that make this statement true 6.x 17+4x 4x+6三15·x+12(mod17 Solution. By Fermat's Theorem, Io= 1 (mod 17). Thus, we can reason as follows 6x2+4x0-4x+6≡2(x)2-6r(x)+416-4x+6(mod17) 2-6x+4-4x+6(mod17) -2x+12(mod17 (c) In the box, write the smallest positive integer that makes this statement true There exist integers s and t such that 117+t·153=x and only if x≡0(mod9 Solution. Recall that an integer r is expressible as a linear combination of a and b if and only if a is a multiple of ged(a, b), i.e. a =0(mod ged(a, b)). In this case, Euclids algorithm gives gcd(153,117)=gcd(117,36)=gcd(36,9)=9
Quiz 1 7 Problem 4. [15 points] Fill in the boxes below. All variables denote integers. No explanations are required, but we can only award partial credit for an incorrect answer if you show your reasoning. (a) Suppose x is a multiple of 17. Write the smallest nonnegative integers that make this statement true. 2x 32 − 6x 17 + 4x 16 − 4x + 6 ≡ 0 · x + 6 (mod 17) Solution. If x is a multiple of 17, then x ≡ 0 (mod 17). Therefore, all terms involving x on the left are congruent to zero. (b) Now suppose x is not a multiple of 17. Write the smallest nonnegative integers that make this statement true. 2x 32 − 6x 17 + 4x 16 − 4x + 6 ≡ 15 · x + 12 (mod 17) Solution. By Fermat’s Theorem, x 16 ≡ 1 (mod 17). Thus, we can reason as follows: 2x 32 − 6x 17 + 4x 16 − 4x + 6 ≡ 2 x 162 − 6x x 16 + 4x 16 − 4x + 6 (mod 17) ≡ 2 − 6x + 4 − 4x + 6 (mod 17) ≡ −2x + 12 (mod 17) ≡ 15x + 12 (mod 17) (c) In the box, write the smallest positive integer that makes this statement true: There exist integers s and t such that s · 117 + t · 153 = x if and only if x ≡ 0 (mod 9 ) Solution. Recall that an integer x is expressible as a linear combination of a and b if and only if x is a multiple of gcd(a, b), i.e. x ≡ 0 (mod gcd(a, b)). In this case, Euclid’s algorithm gives: gcd(153, 117) = gcd(117, 36) = gcd(36, 9) = 9
Problem 5. [15 points] Let p, q, and r be distinct primes. Prove that there exist integers a, b, and c such that: a·(p)+b·(qr)+c·(rp)=1 Hint: First, consider linear combinations of just pq and qr. Solution. Since gcd(pq, qr)=g, there exist integers s and t such that s(pq)+t(ar)=q Now gcd(q, rp)=l, so there exist integers u and v such that uq+v(rp) Therefore u(s(py)+t(qr)+v(rp)=(us)(pq)+()(qr)+v(rp)=1
Quiz 1 8 Problem 5. [15 points] Let p, q, and r be distinct primes. Prove that there exist integers a, b, and c such that: a · (pq) + b · (qr) + c · (rp) = 1 (Hint: First, consider linear combinations of just pq and qr.) Solution. Since gcd(pq, qr) = q, there exist integers s and t such that: s(pq) + t(qr) = q Now gcd(q, rp) = 1, so there exist integers u and v such that: uq + v(rp) = 1 Therefore: u(s(pq) + t(qr)) + v(rp) = (us)(pq) + (ut)(qr) + v(rp) = 1
Problem 6. [15 points] In a chicken tournament, for every pair of chickens u and u, either u pecks v or v pecks u, but not both. A king is a chicken u such that for every other chicken U, either · pecks u,or u pecks a chicken w and w pecks u Complete the proof of the following theorem. Theorem. If chicken c is pecked, then c is pecked by a king Proof. Let Sc be the set of all chickens pecked by c, and let De be the set of all chickens that peck c. The situation is illustrated below (Hint: Apply the King Chicken Theorem to De. If chicken c is pecked, then the set D is nonempty. Thus, there is a tournament among the chickens in De, which has a king by the King Chicken Theorem. We will show that d is actually a king of the original tournament d pecks every chicken in De(directly or indirectly), since it is a king of D d pecks chicken c directly, since d is in Dc d pecks every chicken in Sc indirectly, since it pecks c and c pecks every chicken in
Quiz 1 9 Problem 6. [15 points] In a chicken tournament, for every pair of chickens u and v, either u pecks v or v pecks u, but not both. A king is a chicken u such that for every other chicken v, either • u pecks v, or • u pecks a chicken w and w pecks v. Complete the proof of the following theorem. Theorem. If chicken c is pecked, then c is pecked by a king. Proof. Let Sc be the set of all chickens pecked by c, and let Dc be the set of all chickens that peck c. The situation is illustrated below: S D c c c (Hint: Apply the King Chicken Theorem to Dc.) If chicken c is pecked, then the set Dc is nonempty. Thus, there is a tournament among the chickens in Dc, which has a king by the King Chicken Theorem. We will show that d is actually a king of the original tournament. • d pecks every chicken in Dc (directly or indirectly), since it is a king of Dc. • d pecks chicken c directly, since d is in Dc. • d pecks every chicken in Sc indirectly, since it pecks c and c pecks every chicken in Sc