Home
Course | Math 170: Ideas in Mathematics Spring 2016 |
Instructor | Emanuel Lazar LRSM 324 |
Lectures | MWF 12:00-12:50pm DRL A4 |
Office hours | Mondays 1-2pm, Wednesdays 1-2pm |
Teaching Assistant | Dominick Villano DRL 4C13 |
Recitations | Tuesday 8:30-9:20am Tuesday 9:30-10:20am Thursday 8:30-9:20am Thursday 9:30-10:20am DRL 4C8 |
Office hours | Wednesdays 10-11am, Thursdays 5:30-6:30pm |
Topics | Cardinality of sets, rationals and reals, prime numbers, methods of proof, modular arithmetic, graphs, coloring theorems, Euler and Hamiltonian circuits, polyhedra and the Platonic solids, groups and symmetries, other topics as time and interest permit. |
Book | The Language of Mathematics: Making the Invisible Visible, by Keith Devlin |
Syllabus | http://www.math.upenn.edu/~mlazar/math170/syllabus.pdf |
Exams | Midterm 1: Monday, February 15 Midterm 2: TBA Final: Monday, May 2 @ 9am in Towne 100 |
Overview
Learning to calculate is to mathematics what learning to read is to literature -- necessary, though not especially interesting. In school, most of us took math classes in which we learned to do something (e.g., multiply numbers, solve for x, take derivatives), and then spent months improving our technique. At the end of the day, though, performing these calculations is neither thought-provoking nor particularly useful, as your smartphone can perform them many times faster than even the fastest mathematician.Instead of focusing on calculation, this course will take us on a guided adventure through some of the most beautiful ideas in classical and contemporary mathematics. These ideas have intrigued many of history's most creative minds, inspired them to think deeply about what might appear trivial, and ultimately contributed towards our collective understanding of the world. Despite requiring no prerequisites beyond an elementary-school education, this course will cover some of the most central topics in modern mathematics, including cardinality, prime numbers, geometry, and symmetry groups. In the end, it is the capacity for careful thought, not the ability to precisely and quickly calculate, that is the primary concern, and lasting contribution, of mathematical thinking.
Homework: A problem set will be assigned most weeks. The first part of each assignment is designed to ensure your comprehension of the basic material covered in class; the second part will require more thinking and is designed to facilitate your own mathematical development beyond basic comprehension. In general, assignments will be due at least one week after they are assigned. Late submissions cannot be accepted, though I will drop your two lowest scores. Solutions must be clearly written; if you need to, first work out all solutions on scrap paper, and then carefully rewrite your work on the paper you eventually hand in. Assignments must be turned in on paper.
Working Together: At its best, learning is a collaborative effort, and so students are strongly encouraged to work together on assignments. That said, merely copying another person's work does not involve working -- or learning -- and is not allowed. Each student must turn in a separate copy of the solutions.
Quizzes and Exams: Ten-minute quizzes will be administered most Wednesdays; studying for these is not necessary. There will be two mid-term exams (February 15 and TBA) and one final exam. If you are unable to take an exam as scheduled, please notify me in advance.
Writing Assignments: There will be one or two writing assignments during the semester; more details will be provided later.
Grading: Your final grade will be determined based on the following:
Homework | 200 points (10 assignments, 20 points each) |
Quizzes | 100 points (10 quizzes, 10 points each) |
Exams | 150 points (3 exams, 50 points each) |
Writing Assignments | 50 points |
Expectations: Watching movies will not land you a job in Hollywood, nor will sitting and watching workout videos get you in shape. Likewise, merely watching me and Dominick explain material and solve problems will not make you into a good mathematician. The most important element in your own learning is the time you spend thinking about problems. Don't forget this.
Help: Learning mathematics is hard. Do not feel bashful to ask for help when you do not understand something or feel that you are falling behind. If you cannot make it to scheduled office hours, please be in touch to set up an alternate time to meet. In addition to meeting with me and Dominick, please avail yourselves of the many Penn help resources, including the Math Centers, the Tutoring Center, and the Weingarten Learning Resources Center. Additional information can be found at https://www.math.upenn.edu/ugrad/.
Extra Credit: I will occasionally mention particularly challenging problems, and will post these to the course webpage. A solution for such a problem will be rewarded with extra credit towards the final grade; these points will not affect any curve for the class. In addition, I will also periodically describe special problems, the solution to any of which will be rewarded with an A in the course.
Syllabus
1 | W 1/13 | Introduction, representing numbers, sign-value systems, Roman numerals |
2 | F 1/15 | Roman numerals, positional number systems, decimal number system |
M 1/18 | NO CLASS | |
3 | W 1/20 | Positional number systems, decimal, binary, and other bases |
4 | F 1/22 | Sets, ∩, ∪, ∈, ∉, N, Z, Q |
5 | M 1/25 | Sets, ⊂, set-builder notation, cardinality |
6 | W 1/27 | Definitions, size of a set, cardinality, 1-to-1 matchings between sets |
7 | F 1/29 | Cardinality, countable sets, real numbers |
8 | M 2/1 | Uncountable sets, Cantor, diagonalization |
9 | W 2/3 | Number theory, primes and composites, Euclid's proof |
10 | F 2/5 | Finding primes, Sieve of Eratosthenes, Fermat primes, Goldbach conjecture |
11 | M 2/8 | Fundamental Theorem of Arithmetic, divisibility, Euclid’s Lemma, existence of prime factorizations |
12 | W 2/10 | Uniqueness of prime factorizations, introduction to mathematical induction |
13 | F 2/12 | Review of number systems, sets, cardinality, and prime numbers |
14 | M 2/15 | FIRST MIDTERM EXAM |
15 | W 2/17 | Introduction to Graph Theory |
16 | F 2/19 | Graphs, vertex degrees, connected, k-regular, and complete graphs |
17 | M 2/22 | Graph isomorphism |
18 | W 2/24 | Planar and non-planar graphs |
19 | F 2/26 | Polyhedral graphs and the Platonic solids |
20 | M 2/29 | Platonic solids, dual graphs and dual polyhedra |
21 | W 3/2 | Duals, soccer balls, map colorings |
22 | F 3/4 | Map colorings, 6-color graph theorem |
SPRING BREAK | ||
23 | M 3/14 | Euler paths and cycles, Bridges of Konigsburg |
24 | W 3/16 | Hamiltonian paths, applications |
25 | F 3/18 | Review of graph theory |
26 | M 3/21 | SECOND MIDTERM EXAM |
27 | W 3/23 | Secure communication, encryption, ciphers, modular arithmetic |
28 | F 3/25 | Modular arithmetic: addition |
29 | M 3/28 | Modular arithmetic: multiplication, remainders, dividing by 9 |
30 | W 3/30 | Modular arithmetic: exponentiation |
31 | F 4/1 | Fermat's Little Theorem, secret colors |
32 | M 4/4 | Diffie-Helmann key exchange |
33 | W 4/6 | Random numbers |
34 | F 4/8 | Linear congruent generators |
35 | M 4/11 | Symmetry and binary operators, closure, identity elements |
36 | W 4/13 | Binary operators, inverses, associativity, group definition |
37 | F 4/15 | Modular groups, geometric groups, braid theory |
38 | M 4/18 | Group order, group isomorphism |
39 | W 4/20 | Symmetry groups of shapes, cyclic groups, dihedral groups |
40 | F 4/22 | Symmetry groups of the Platonic solids |
41 | M 4/25 | * Special lecture * |
42 | W 4/27 | Review |
M 5/2 | FINAL EXAM, 9AM, Towne 100 |
Homework
Below are listed the weekly assignments, and the due date for each. Questions and answers about the homework assignments and midterms can be found here.Assignment 1 | January 22 | Solutions |
Assignment 2 | February 1 | Solutions |
Assignment 3 | February 8 | Solutions |
Assignment 4 | February 12 | Solutions |
Assignment 5 | February 29 | Solutions |
Assignment 6 | March 14 | Solutions |
Assignment 7 | March 18 | Solutions |
Assignment 8 | April 4 | Solutions |
Assignment 9 | April 11 | Solutions |
Assignment 10 | April 18 | Solutions |
Assignment 11 | April 25 | Solutions |
Writing assignment | April 27 |
Quizzes. Ten-minute quizzes are administered most Wednesdays; studying for these is not necessary.
Quiz 1 | Quiz 2 |
Quiz 3 | Quiz 4 |
Quiz 5 | Quiz 6 |
Quiz 7 | Quiz 8 |
Quiz 9 | Quiz 10 |
Misc
Lecture Notes and Additional Material I will periodically add notes and references to interesting readings related to our discussions during the lectures. If you do notice mistakes, please let me know.Lecture notes 1 -- Number Systems | ||
Lecture notes 2 -- Sets | ||
Lecture notes 3 -- Cardinality | ||
Lecture notes 4 -- Prime Numbers | ||
Lecture notes 5 -- Graph Theory 5.1 Intro and Basics 5.2 Isomorphism 5.3 Planar Graphs and Euler's Formula 5.4 Polyhedral Graphs and the Platonic Solids 5.5 Map Colorings 5.6 Euler Paths and Cycles |
||
Lecture notes 6 -- Modular Arithmetic and Applications 6.1 Intro to Encryption 6.2 Modular Arithmetic Basics 6.3 Modular Exponentiation 6.4 Diffie-Hellman Key Exchange 6.5 Random Numbers |
||
Lecture notes 7 -- Symmetry and Group Theory 7.1 Shapes and Symmetries 7.2 Binary Operators 7.3 Groups 7.4 Symmetry Groups of Shapes |
||
Here is a beautiful article by Dieter Kotschick entitled "The Topology and Combinatorics of Soccer Balls", published in Scientific American. Some of the material in the article overlaps with what we have already covered in class, but there is much much more which we could not cover. |
||
Here is a beautiful article by Brian Hayes entitled "Graph Theory in Practice", published in Scientific American. This article provides some overview of Graph Theory, with attention paid to applications in understanding social networks. Notice that it was printed in 2000, several years before Facebook was founded. |
||
Here is a beautiful article by Brian Hayes entitled "Connecting the Dots", published in Scientific American. This article provides some overview of the role that graph theory, and complete graphs in particular, play in national security. |
||
Some notes and exercises related to sets can be found in Book of Proof, by Richard Hammack. In particular, Sections 1.1, 1.3, and 1.5 discuss sets, set-builder notation, subsets, unions, and intersections; solutions to all exercises can be found in the back of the book. |
||
The following website has several tools for converting numbers from one base to another. |
Extra Credit Problems. The problems below are more challenging than those we have considered so far in class. A correct solution for any of them will be awarded with 5 extra points towards the final grade.
1 | Prove that it is possible to draw a circle centered at (√ 2, 1/3) that contains any number of points of the form (a,b) where a and b are both integers. This can be used to show that for any number of points n, a circle can be drawn in the plane that encloses exactly n lattice points. |
2 | In class we proved that every planar graph could be colored using 6 colors in such a way that any pair of vertices connected by an edge are colored differently. Write up a nice proof that every planar graph can be colored using only 5 colors. Proofs can be found in many places online. |
Open Problems. The problems are below are "open", which means that so far they have not been solved. Solution of any of these problems will be rewarded with an A in the course. Work reflecting serious thinking about any of these problems, even if they do not lead to a solution, will be awarded with extra credit.
1 | Start with a positive whole number n. If it is even, divide it by two; if it is odd, multiply it by 3 and add 1. Repeat over and over. Do you always eventually get to 1? | Additional Information |
2 | In class we learned that the square root of 2 cannot be written as the ratio between two whole numbers -- the proof was relatively simple. Although it is known that π and e are also irrational, and it is easy to show that at least one of π+e or π*e is irrational, it is not known whether both π+e or π*e are irrational. Is one of them rational? | |
3 | In class we learned that there are infinitely many prime numbers. We also noticed many pairs of primes seperated by 2. For example 3 and 5, 5 and 7, 11 and 13, 17 and 19, and so forth are pairs of primes that are 2 apart. Are there an infinite number of such pairs? | Additional Information |
4 | In class we proved that every natural number greater than 11 can be written as the sum of two composite numbers. One of the oldest problems in number theory is about sums of prime numbers -- can every even number greater than 2 be written as the sum of two primes? | Additional Information |
5 | On a homework you were asked to illustrate all possible trees (up to isomorphisms) on n = 5 and n = 6 vertices. How many such trees are there? For 5 and 6 vertices, there are 3 and 6 trees, respectively. What is the story for other values of n? No closed formula is known to answer this question. | Additional Information |
6 | In class we proved that every planar graph could be colored using 6 colors in such a way that any pair of vertices connected by an edge are colored differently. Proving this with only 5 colors is not terribly complicated. However, while it is known that every planar graph is also 4-colorable, the proof of that theorem is very complicated. A simpler proof is highly desirable. | Additional Information |