Problem 1Problem 2Problem 3Problem 4Massachusetts Institute of Technology 6.042J/18.062J, Spring ’10: Mathematics for Computer Science March 17 Prof. Albert R. Meyer revised March 18, 2010, 1193 minutes Problem Set 7 Due: April 2 Reading: Notes Ch. 12; Ch. 14 Problem 1. A simple graph is sevenish when it has no simple cycles of length less than seven. A map is a planar graph whose faces are all simple cycles (no dongles or bridges). Let M be a sevenish, connected, map with v > 2 vertices, e edges and f faces. (a) Prove that e ≤ (7v − 14)/5. (1) Hint: Similar to the proof of Corollary 12.6.3, that e ≤ 3v − 6 in planar graphs. (b) Show that M has a vertex of degree at most two. (c) Part (b) can be used to prove that M is 3-colorable by induction on v. The proof is slightly complicated by the fact that subgraphs of M may not be sevenish, connected, maps. For each of the following properties, briefly explain why all connected subgraphs of M have the property, or give an example of a connected subgraph of an M that does not have the property. 1. map 2. planar 3. sevenish 4. connected 5. 3-colorable Problem 2. Prove that the greatest common divisor of three integers a, b, and c is equal to their smallest positive linear combination; that is, the smallest positive value of sa + tb + uc, where s, t, and u are integers. Problem 3. Two nonparallel lines in the real plane intersect at a point. Algebraically, this means that the equations y = m1x + b1 y = m2x + b2 Creative Commons 2010, Prof. Albert R. Meyer.2 Problem Set 7 have a unique solution (x, y), provided m1 =� m2. This statement would be false if we restricted x and y to the integers, since the two lines could cross at a noninteger point: However, an analogous statement holds if we work over the integers modulo a prime, p. Find a solution to the congruences y ≡ m1x + b1 (mod p) y ≡ m2x + b2 (mod p) when m1 �≡ m2 (mod p). Express your solution in the form x ≡? (mod p) and y ≡? (mod p) where the ?’s denote expressions involving m1, m2, b1, and b2. You may find it helpful to solve the original equations over the reals first. Problem 4. Let Sk = 1k + 2k + . . . + (p − 1)k, where p is an odd prime and k is a positive multiple of p − 1. Use Fermat’s theorem to prove that Sk ≡ −1 (mod p).Massachusetts Institute of Technology Solutions cover sheet 6.042J/18.062J, Spring ’10: Mathematics for Computer Science March 17 Prof. Albert R. Meyer Student’s Solutions to Problem Set 7 Your name: Due date: April 2 Submission date: Circle your TA/LA: Megumi Tom Richard Eli Collaboration statement: Circle one of the two choices and provide all pertinent info. 1. I worked alone and only with course materials. 2. I collaborated on this assignment with: got help from:1 and referred to:2 DO NOT WRITE BELOW THIS LINE Problem Score 1 2 3 4 Total Creative Commons 2010, Prof. Albert R. Meyer. 1People other than course staff. 2Give citations to texts and material other than the Spring ’10 course materials.MIT OpenCourseWarehttp://ocw.mit.edu 6.042J / 18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...