DOC PREVIEW
MIT 6 042J - Quiz 1

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Problem 1(a)(b)(c)Problem 2(a)(b)(c)Problem 3(a)(b)Problem 4(a)(b)(c)Problem 5Problem 66.042/18.062J Mathematics for Computer Science March 9, 2005Srini Devadas and Eric LehmanQuiz 1YOUR 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 theback of the sheet containing the problem.• Be neat and write legibly. You will be graded not only on the correctness of youranswers, but also on the clarity with which you express them.• The exam ends at 9:30 PM.• GOOD LUCK!Problem Points Grade Grader1 202 153 204 155 156 15Total 100Quiz 1 2Problem 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 onlyimplications 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.Quiz 1 3(b) Let S be the set of all people, and let M (x, y) be the predicate, “x is the mother ofy”. 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 andpredicate M defined above.“Everyone has a mother.”∀x ∃y M (y, x)Quiz 1 4Problem 2. [15 points] Complete this proof that n cents of postage can be formed using 3and 5 cent stamps for all n ≥ 8.Proof. We use strong induction.(a) Let P (n) be the proposition thatSolution. 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 + 39 = 3 + 3 + 310 = 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 stampgives 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.Quiz 1 5Problem 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—dand none of the edges a—c, a—d, b—c, or b—d.wwwwabcd2. Delete edge c—d and add edges a—c and a—d:@@@@@@@@wwwwabcd(a) In the box on the right, draw a graph that can be obtained by tweaking the graphon the left.HHHHHHHHHHHHHHwwwwww123456→HHHHHHHHHHHHHHHHHHHHHHHHHHHwwwwww123456Quiz 1 6(b) Suppose that G0is an undirected graph with an Euler tour. Also, suppose G1isobtained by tweaking G0, G2by tweaking G1, and so forth. Use induction to provethat every graph Gnobtainable 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 isconnected and every vertex has even degree.Solution. We use induction. Let P (n) be the proposition that Gnhas an Euler tour.Base case. G0has an Euler tour by supposition.Inductive step. For n ≥ 0, we assume Gnhas an Euler Tour and prove that Gn+1alsohas an Euler tour. Specifically, we show that Gn+1has only even-degree vertices andis connected:• Every vertex in Gnhas even degree, since Gnhas an Euler tour. Every vertexin Gn+1has the same degree, except for vertex a which has degree two greater.Thus, every vertex in Gn+1has even degree.• Consider arbitrary vertices u and v in Gn+1. Since Gnis connected, there is apath from u to v in Gn. If the path does not contain c—d, then the same pathexists in Gn+1. If the path does contain c—d, then there is a corresponding pathin Gn+1where c—d is replaced by edges c—a and a—d.This implies Gn+1has an Euler tour as well. Therefore, Gnhas an Euler tour for alln ≥ 1. In particular, G6042has an Euler Tour.Quiz 1 7Problem 4. [15 points] Fill in the boxes below. All variables denote integers. No expla-nations are required, but we can only award partial credit for an incorrect answer if youshow your reasoning.(a) Suppose x is a multiple of 17. Write the smallest nonnegative integers that makethis statement true.2x32− 6x17+ 4x16− 4x + 6 ≡ 0 · x + 6 (mod 17)Solution. If x is a multiple of 17, then x ≡ 0 (mod 17). Therefore, all terms involvingx on the left are congruent to zero.(b) Now suppose x is not a multiple of 17. Write the smallest nonnegative integersthat make this statement true.2x32− 6x17+ 4x16− 4x + 6 ≡ 15 · x + 12 (mod 17)Solution. By Fermat’s Theorem, x16≡ 1 (mod 17). Thus, we can reason as follows:2x32− 6x17+ 4x16− 4x + 6 ≡ 2x162− 6xx16+ 4x16− 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 thats · 117 + t · 153 = xif and only ifx ≡ 0 (mod 9 )Solution. Recall that an integer x is expressible as a linear combination of a and bif 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) = 9Quiz 1 8Problem 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 · (q r) + 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) = qNow gcd(q, rp) = 1, so there exist integers u and v such that:uq + v(rp) = 1Therefore:u(s(pq) + t(qr)) + v(rp) = (us)(pq) + (ut)(qr) + v(rp) = 1Quiz 1 9Problem 6. [15 points] In a chicken


View Full Document

MIT 6 042J - Quiz 1

Documents in this Course
Counting

Counting

55 pages

Graphs

Graphs

19 pages

Proofs

Proofs

14 pages

Proofs

Proofs

18 pages

Proofs

Proofs

18 pages

Quiz 2

Quiz 2

11 pages

Load more
Download Quiz 1
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Quiz 1 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Quiz 1 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?