Questions and answers about the homework assignments and midterms will be posted here; the more questions that are asked, the more answers will be posted. Feel free to submit questions here.

Grading questions
The writing assignment will count for 10% of the grade, the quizzes for 20%, the exams 30%, and the homework assignments 40%. We will drop the lowest two homework scores, and two quizzes will be dropped. In previous semesters, this grading scheme resulted in roughly 65% of the class receiving a grade in the A/A- range, so no curve seemed appropriate.

Final exam

Proofs
Proofs of the theorems you should know are available here.

Will section 6.5 (on random numbers) be tested on the exam. You wrote that the ideas in probability will not be.
The first half of Section 6.5 will not be tested; the second half, the part about generating random numbers, will be.

If a = b (mod m) and c = d (mod m), then a - c = b - d (mod m). You said this was true. However, if a = b (mod m) and c = d (mod m), then this means a + c = b + d (mod m). I don't understand how this is equivalent to a - c = b - d (mod m).
Both of these are true. Consider, for example, the two statements x=5 and y=3. The rules of classical arithmetic allow us to obtain new statements from these old ones. In particular, we can figure out that x+y = 5+3, and we can also figure out that x-y = 5-3. Modular arithmetic behaves in the same way.

Do we need to be able to show using modular arithmetic that you can determine whether a large number is divisible by 9 by adding its digits?
No.

Can we use a calculator for the exam?
No.

Do we need to be able to show why periods of repeating patterns must be (m-1) or less?
No.

Do we have to know how to generate random numbers using increments?
No.

Do we need to be able to show using modular arithmetic that you can determine whether a large number is divisible by 9 by adding its digits?
No.

So we do not need to know anything about associativity except for the fact that addition and multiplication are both associative?
There will be no questions about associativity on the exam.

Do we need to know about counting symmetries through coloring?
No.

Do we have to know how to do a problem such as problem #6 on HW #9? I.e. do we need to know how to find the last 2 digits of a problem?
Yes -- you should understand that finding the last two digits of a number N is equivalent to finding N mod 100, and be able to make such computations.

For the Platonic solids, do we need to know anything more than the rotational axes of each order (e.g. question 7 from Homework 11)?
Understanding the rotational symmetries, as described in this question, will be sufficient for the exam. We did not have enough time to study in depth the complete symmetry groups of the Platonic solids.

How can we tell if a shape has rotational symmetries? How can we tell if a shape has mirror symmetries?
For our purposes, a rotational symmetry is a way of rotating a shape without the end result looking different. For example, a square can be rotated about its center by 90 degrees without changing the way it looks; if it were rotated by 73 degrees, for example, we would notice that it was changed. A rectangle (that is not also a square) has only the 0 and 180 degree rotations. A mirror symmetry is a way of reflecting a shape through a mirror passing through it, again in such a way that leaves it looking unchanged. For example, a rectangle (that is not also a square) has exactly two mirror symmetries, each passing through the center and parallel to two sides.

Does every n-gon have n rotational symmetries and n mirror symmetries?
Every regular n-gon has n rotational symmetries and n mirror symmetries. If the n-gon is not regular, though, the number of rotational and mirror symmetries will be less than n. Consider a non-square rectangle as such an example.

Do we need to know about the properties of random numbers or just about random number generators & how to generate random numbers?
You will not be asked anything about random numbers aside from random number generators and how to use them.

Do we have to know how to find the square roots of a modulus as we did in problem #8 from HW assignment #8?
No -- there will be no questions about square-roots on the exam.

Will we need to understand group isomorphism for the exam?
No -- there will be no questions about group isomorphism on the exam.

Writing Assignment

For the writing assignment, can we write in the first person?
Good writing comes in all kinds - first, second, third, fourth, fifth person, etc, are all acceptable.

For the writing assignment, is the page range 1-4 pages double spaced or single spaced?
Either. If you can do a solid job in one page, double-spaced, that would be perfectly ok. If it takes you four pages of single-spaced writing, that would be fine too. If you have 4 single-spaced pages worth of material, use 4 single-spaced pages to say it; if you have only 1 double-spaced page worth of material, don't use more than 1 double-spaced page to say it.

Homework 11

Part one includes operators such as "a + b," In class we haven't phrased it this way; it's always been just "multiplication," "addition," "combination," etc. Does this mean that a and b must be different elements of the set - and, consequently, that for the homework elements cannot be their own inverses as they have been in class?
I am sorry for any confusion I may have caused -- a and b can be the same element of the set; consequently, they can be their own inverses. The variables a and b represent any elements in the given set and, as usual, it might be the case that a=b.

What do you mean by list symmetry groups in order of decreasing popularity?
Suppose that of the 25 car tire sets you considered, you saw tire rims with symmetry group D_5 more than those with symmetry group C_7, then D_5 should be listed before C_7. Tabulate your results means that you should also indicate the frequency of each observed type. For example, perhaps you observed D_5 8 times, C_7 5 times, etc.

Homework 10

I started to work on problem number two and am unsure how many values I need to calculate? I have 8 pairs plotted on my graph, but am unsure how many you are looking for.
There should be 22 distinct numbers (if s=11, for example, then we should have 11, 6, 20, 13, 5, 9, etc), and so you should plot 22 points on this graph. For example, we would have points (11,6), (6,20), (20, 13), etc.

For problem 2, what are the x and y axes supposed to represent?
Here the x and y axes do not represent anything more than the regular number line. If you plot the points correctly, you will notice that they all lie on two parallel lines, and so despite the numbers 11, 6, 20, 13, 5, 9, ... appearing relatively "random", in some sense they are very non-random. The spectral test (the details of which we did not cover) was designed to quantify this lack of randomness, to help test which LCG are "more random" than others.

For question four, should the random numbers generated between 0 and 1 be rational, irrational, or a combination of rational and irrational?
In short, rational. In general, an irrational number requires an infinite amount of memory to store, and since computers only have a finite amount of memory (megabytes, gigabyets, etc), they can't really represent irrational numbers. For most practical purposes, rational numbers are adequate for calculations, even when the real problem under consideration involves irrational numbers.

I've spent a lot of time thinking about number 5 but am still having trouble coming up with a way to generate integers from an LCG than normally gives fractions. Could you perhaps please direct us to a hint for this question?
Normally, LCG's are used to generate integers, but in many applications we want numbers that look like irrational numbers. Excel, your calculator, and other computer programs use LCG's to generate such numbers. What happens if you generate random integers between 0 and 99, and then divide each one by 100? What sort of random numbers do you get? More generally, how would you use an LCG with modulus m to generate random numbers between 0 and 1?

General questions

What resources to do you recommend that we use for these homeworks? Many of the concepts are briefly mentioned in class and in the notes online, however, there is a gap between this knowledge and that required on the homework.
The internet is chock-full of high-quality mathematical content, but knowing where to find it can be difficult. In general, almost anything you find on wikipedia should be deemed reliable. In general, ideas that arise in the homework problems have been discussed in class (sometimes more than once) and are also discussed in the course notes I post online. But since the class is meant to spur independent thinking, and is not designed to encourage rote memorization and application of formulas, I often like adding questions that require independent thinking. Dominick and I are always happy -- before class, during class, after class, during recitations, during office hours, via email -- to help provide additional help when you guys get stuck. I almost always give you at least a week worth of time to think about these problems and to ask us for help when needed. I'm not sure what else we can do in this direction, other than settling on merely asking you to memorize material and regurgitate it, which I do not believe facilitates true learning. If you have better suggestions, please feel free to follow up.

(1) My partner and I have been working on homeworks for over 2 hours and are still having troubles coming up with answers for many of the homework problems. Is there a way to still get credit for the questions, even if we do not have the correct answer?
(2) You mentioned in class that we can get full credit for explaining our logic, even though we did not necessarily have the correct answer. For previous homeworks, this has not been the case. How can we ensure that we can get the full credit?
I have mentioned several times in class that we will award full credit if you demonstrate a sincere attempt to understand and solve a problem, even if you do not arrive at the final correct solution. Demonstrating this sometimes involves taking a few sentences to describe what you tried, why you tried it, and why it did not work out as you had hoped. Neither Dominick nor I are prophets nor mind-readers, so if you just write a short incorrect answer, we have no way of knowing whether you spent the whole week thinking about this and this is what you got, or whether you spent five minutes the night before the assignment was due and this was the first thing that came to mind. We try hard to grade fairly and generously but sometimes make mistakes. If you did spend time on the problem, make that clear on your submitted response and we will grade as generously as we can.

Homework 9

The wording of question 5 was slightly confusing and I have changed it; specifically, I have replaced a variable a with the variable g.

Homework 8

I am a little confused about the structure of the multiplication table. The structure of mod is B - A = kM, where M is the mod. How does the multiplication table work? If it is 2 x 3. Does this mean A=2, B=3, M=7, then you put the value for k? Or does this mean A= 2 x 3, M=7 and you solve for B?
In a regular multiplication table you, you multiply the number at the beginning of a row with the number at the top of the column. Here you do the same, but then take the remainder after dividing by the modulus; the value of k is not important. For example, a=2 and b=3, then you fill in 6. If a=3 and b=3, then you would fill in 2, because 3*3 = 9 ≡ 2 mod 7. If a=5 and b=4, then we have 5*4 = 20 ≡ 6 mod 7, so we would fill in 6.

Midterm 2

This is a general question about planarity and isomorphisms: in the class notes it says "we can ensure that planarity is preserved under isomorphisms." Does this mean that another condition of 2 graphs being isomorphic is that they both have to be planar (meaning they can both be drawn w/ no 2 edges crossing) or that they both have to be not planar?
Yes, it is indeed the case that two isomorphic graphs are either both planar or both non-planar. Likewise, two isomorphic graphs are either both connected or both not connected, both regular or both not regular, both bipartite or both not bipartite. Two isomorphic graphs can either both be colored "nicely" with 6 colors or can both not be colored "nicely" with 6 colors. Both have an Euler cycle or neither have an Euler cycle. The pattern here is that for all interesting properties of a graph, either two isomorphic graphs have that property or neither have it.

In proving that every planar graph can be colored with at most 6 colors, will we also need to prove that every planar graph has a vertex with degree at most 5?
No, you will not need to prove that every planar graph has a vertex with degree at most 5, and can take this for a given; if I use this question on the exam, I will make this point clear.

Just confirming, we don't have to know the proof about only 5 existing regular polyhedra for the midterm, right?
Right. You should know that there are five and should know what they are, but you will not be asked to prove that there are only five.

Will we have to draw graphs on the midterm?
I haven't written the exam yet, but there is a good chance I will ask you to draw at least one graph.

Are all disconnected graphs planar?
Yes, since you can draw these in such a way that edges never cross. It helps that there are no edges.

Is there a difference between saying two graphs are the "same" and two graphs are "isomorphic?" Or using an equals sign versus isomorphic sign?
Yes/no. Consider the two graphs given by G1 = ({a,b}, {{a,b}}) and G2 = ({1,2}, {{1,2}}), where the first sets are the vertices and the second sets are the edges. Of course as sets these are different, so technically these are different graphs. In graph theory, though, people often use the words same and isomorphic interchangeably, because for all graph-theoretic purposes these graphs are the same. For example someone might call both of these K_2, and in this sense K_2 does not refer to a specific labeling of a graph, but to all graphs that have 2 vertices and 1 edge.

I know it is not one of the selected proofs, but I am wondering if it could come up anywhere else on the exam.
You do not need to know the soccer ball proof.

What do we need to know--if anything--about the equation 1+2+3+4...+n=n(n-1)/2?
You don't need to know anything about this equation.

Just to clarify, there will be no induction besides the induction needed for the 6-color proof? Does this mean we would have nothing like the last question on HW 7?
Right, I was somewhat self-contradictory. You should know the induction step necessary for the 6-color proof, but otherwise not need to know it for these summation proofs.

I am having trouble with part of the first proof that we need to know for the midterm on. I understand why k (sub5) is non-planar using Euler's theorem (because of the resulting contradiction). But the same does not seem to apply for the other non-planar graph: k (sub3,sub3). It seems like I need more than just the formula but I can't figure out what I am missing. Do you have any guidance?
For K_{3,3}, we use a similar approach at the beginning. That graph has 6 vertices and 9 edges, so if it were planar, Euler's formula would require that it have 5 faces. How many edges does each face have? Every face in any planar graph must have at least 3 edges, and since this graph is bipartite, each face must have an even degree (HW 6, Q6), so each face must have degree at least 4. Therefore, the sum of degrees of all 5 faces must be at least 20, meaning there must be at least 10 edges in the system (since the sum of face degrees equal twice the number of edges). But this graph has only 9 edges, which is less than 10.

To prove K5 or K3,3 is non-planar, is it okay to simple state that each face is bounded by at least 3/4 edges or do we need to expand and explain why it is only bounded by these many edges?
You should provide a short explanation of why the minimum number of faces per edge is 3 or 4; one or two sentences should be sufficient.

Is K{3,3} both a complete AND a bipartite graph?
This answer is a bit tricky, but not important to know for the exam. K{3,3} is a bipartite graph, but not a complete graph. A complete graph is a graph with an edge connecting every pair of vertices; a complete graph on n vertices has n(n-1)/2 edges. Even though K{3,3} has 6 vertices, it does not have 15 edges. K{3,3} is sometimes called a "complete bipartite" graph because it has all possible edges while still being bipartite. In particular, every vertex of one set (of 3 vertices in this case) is connected to every vertex in a second set (of 3 vertices in this case).

Does any graph composed of vertices with even degrees definitely have an Euler cycle? Likewise, does every graph composed of vertices with even degrees and at most two vertices with odd degrees definitely have an Euler path?
In short yes, though we should make clear that we are discussing only *connected* graphs, otherwise they will have no Euler path or cycle, regardless of all degrees being even.

Are regular polyhedra and platonic solids the same thing?
Yes.

Do we need to know sum notation for the exam?
No.

Homework 7

Problem 4. I am having an issue getting started with question 4. Any hints as to how to approach this?
There are three parts to this question. For the first, remember that a graph need not have any edges at all. For the second, think about what the maximal degree of a vertex can be. The third part might be the most challenging. What needs to happen for a vertex to have degree n-1? How many other vertices must it be connected to by an edge?

Homework 6

Problem 5. Does a graph need to have any edges at all?
In short, no. The definition of a graph is a pair of sets V and E. V is any set, and we call its elements vertices; elements of E are 2-element subsets of V; we call elements of E "edges". As you probably remember from earlier in the year, an empty set is still a set, and so a graph with 0 edges will still satisfy the definition of a graph. Likewise, the definition of a bipartite graph also does not say anything about how many edges a graph should have, and so a bipartite graph can have 0 edges. Indeed, every graph with 0 edges is bipartite (in fact, you might notice that every graph with exactly one edge is also bipartite).

Problem 6(a). How can a cube be bipartite if all the vertices are connected to all the other adjacent vertices?
The image below is a hint.

Problem 6(b). I’m a bit confused in my approach for problem 6(b). In class, we’ve already proven that for any planar graph, we need each face to have at least degree of 3. So in this case, we’re trying to prove that bipartite planar graphs must have degree of 4. Should I be thinking about this in terms of each face having 3 vertices and not being able to decide which vertices to go to which of the 2 sets we are trying to build?
There are several ways to go about solving this problem. Here is one way. Consider why every face in a bipartite graph must have an even number of edges. Remember that vertices are split into two groups, say A and B, and that every edge takes you from one group to the other. Imagine "traveling" around the edges of a face. To go around the entire face, you must begin and end on the same vertex. Every edge you "switches" you from a vertex in A to a vertex in B to a vertex in A, etc. Notice also that if you begin in A, you must end in A (why?), and likewise for beginning in B. If these hints don't help, please follow up.

Problem 6. How does planar change the definition of bipartite? Can we consider a the "plane" to be the set, instead of individual vertices?
I did not understand the question (in particular the second one) but will try to answer what I can. The definition of bipartite is the same for planar graphs as for non-planar graphs. Whether a graph is planar is determined by whether it can be drawn in a way so that edges do not cross. Whether a graph is bipartite is determined by whether its vertices can be broken into two sets so that edges only connect vertices in opposite groups, but not within the same graph. Some groups are planar, some are bipartite, some are both, and some are neither.

Homework 5

I think that there is a typo in question 6 on the homework. I believe that the expression in the problem should be (n^2 - n)/2, not (n^2 + n)/2.
Of course you are correct, and this is indeed a typo. I have posted a corrected version online.

For problem 2, are we supposed to be using the sums from the previous question, and, if so, is "sum 1" supposed to be "a" (1+2+...+n) and "sum 2" supposed to be "b" and so on? For example, would the answer to the second sub question be 1-2+3=2?
Yes, for each you should use the sum from the previous problem -- Sum 1 meant the sum from 1(a), Sum 2 meant the sum from 1(b), and so forth. The answer for the second sub question would indeed be 2 (=1-2+3).

Do we need to simplify 2c and 2f?
No, you do not need to simplify 2c and 2f, and can leave these in terms of x.

Midterm 1

When doing proofs, is it a given to say that any even number multiplied by an odd is an even number, or do you need to continue the proof farther?
Unless I ask you to prove exactly that point, then it would be enough to leave things at that, and you would not need to prove that an even multiplied by an odd is even. The question makes me wonder what a good proof might be, and I think that the following would be it. If a is even, then a = 2k for some integer k. It follows that for any integer b (odd or even), we have a*b = 2*(b*k), so that an even times any integer is even.

For the mid-term, will we need to be able to convert, or perform operations, in bases greater than 10?
No.

In proving that the square root of 5 is irrational, how did we prove that if sqrt(5)=a/b then a and b must both be odd?
Let's think about what happens if a was even and b was odd. If a is even, then a^2 is also even. If b is odd, then so is b^2, and then so would be 5*b^2. But an even number (a^2) can't equal an odd number (5*b^2), so it's not possible that a be even and b be odd. A similar argument will show that if a is odd and b is even, you will also get a contradiction. Combined, these results show that either a and b are both even or both odd. If both are even, then of course a/b is not in lowest terms / simplest form. Therefore, it must be that if sqrt(5) can be written as a ratio of whole numbers a/b in lowest terms, then it must be that a and b are both odd. The end of the proof shows that this too will lead to a contradiction.

Are there examples/practice problems for proofs about evens and odds?
There are several good examples/practice problems in the exercises at the end of the Chapter 4 in Book of Proof, by Richard Hammack. On page 100, I see that questions 1, 2, 3, 4, 5, 14, and 15 are all about even/odd, and there are solutions in the back of the book.

For the proofs, do we need to explain with whole sentences or can we do out the proof just as we had been doing on HW assignments and have some phrases + sentences interspersed?
Regarding proofs, I think that Dominick's solutions (posted on the course webpage) should serve as a good example of what your proofs should look like. The goal of a good proof is to convince the reader of something, and if the proof consists of only a bunch of equations with unclear motivation and direction, then it might not end up being very convincing. If the ideas behind your proof are clear, then I think we would award full credit even if the writing isn't Shakespeare.

Should we go over making rational repeated decimals into simplest form, such as turning 10.2333.... into simplest form?
You will not need to convert any repeating decimals into simplest form on the exam.

You wrote: "Part C will ask you to prove two of the four theorems below." Does that mean we will get to choose two, or does it mean you will choose two?
The wording was slightly confusing. You should understand all four theorems, and I will ask you to prove two of them on the midterm.

For Part C, you wrote that we will have to "prove that n^3-n+1 is always even." However, n^3-n+1 will always produce an odd number. Would you please clarify this matter?
This was a mistake; it should read "... is always odd."

What do you suggest I go over on my own time to best prepare myself for the exam on Monday?
I suggest that you go over material we covered in class and the homework assignments, focusing on understanding the ideas we covered; I have posted some notes to the course webpage, which you might find helpful. In general I think it will be more efficient to go slower and understand less of the material in greater depth than to try memorizing lots of information quickly.

Homework 4

Can you clarify the wording on assignment 4, problem 2?
You should show that for any natural number n, the numbers n!+2, n!+3, n!+4, ... n!+n are all composite. For example, think about what happens when n=5. We then have n!=5*4*3*2*1=120, and then 122, 123, 124, and 125 are all composite. Show that a similar result holds for any value of n.

Homework 3

I am having some trouble making my ideas for the last problem of part II more concrete. To show countable infinite sets A and B had the same cardinality, it simply sufficed to show that both have elements that can be mapped on a 1-1 basis to the elements in the set of natural numbers. Now, for our case, would f(x) = x + 1 work?
The goal here is to match every element of A with exactly one element of B, *and* every element of B with exactly one element of A. If we have A = (0,1), and a function f(x) sends an element x in A to an element x+1 in B, then there will be elements of B which are not matched with elements in A. For example, there is no element x in A so that f(x) = 5, so 5, which is certainly an element of (0,infinity), would not be matched with anything in A. For A and B to have the same cardinality, we are looking for some matching between every element in A and every element in B that is 1-to-1.

In recitation, Dominick suggested thinking about the graph of a function, and see if you could draw one that matches all elements in (0,1) with all of those in (0,infinity). Thinking about some examples of 1-to-1 functions will help give you additional insight and ideas.

Homework 2

I'm having trouble making the distinction from switching from Base 10 to Base 5 and switching from Base 5 to Base 10. Do you have a direction I could go to be able to understand this easier?
Switching from base 5 to base 10 is probably simpler to do than the reverse, so let's first solve one example to help illustrate what is going on. Suppose we want to convert 1.111, written in base 5, to base 10, then we look at each digit and its position. The digit to the left of the period indicates the number of 1's; the first digit to the right of the period indicates the number of fifths, i.e., 5^(-1) = 1/5, the second digit indicates the number of twenty-fifths, i.e., 5^(-2) = 1/25, and the third digit indicates the number of 5^(-3) = 1/125. Since all digits are 1, we have one of each, so we have 1 + 1/5 + 1/25 + 1/125. A calculator will show you that we can write this in standard base 10 as 1.248.

Switching from base 10 to base 5 requires more thought. As a warmup, consider how to pay $6.47 with the fewest number of bills and coins. First you think about the largest bill you could use. If you tried using a $10, you'd be "going over", so instead you use a $5, and then a $1; next you would use a quarter ($0.25), two dimes (2 x $0.10) and two pennies (2 x $0.01). You can likewise use powers of 5 to represent numbers. In this case your "denominations" are ... 25's, 5's, 1's, fifths, twenty-fifths, etc. Using a 5 would be "go over", so we begin by using only 1's, and then smaller denominations. We can use *one* 1 and *one* fifth to represent 1.2 (= 1 + 1/5), so in base-5 we write that out as 1.1.

I'm having some trouble with problem 3 from part II of HW2.
For two sets A and B to be the same, they must contain the same elements -- every element of A must be an element of B, and every element of B must be an element of A. In this case, it is clear that every element of A is an integer, and hence in B. The more difficult part of the problem is showing that every element in B -- i.e., every integer -- can be written in the form 25a+13b, for integers a and b. As a short hint, think about whether the number 1 can be written in this form. If 25a+13b = 1 for some integers a and b, then can any other integer also be written in this form?

Notice also that I slightly changed the homework assignments from last term, so this question involves 25 and 13 instead of 25 and 12.

Homework 1

How rigorous do we have to be in the homework problems? Do we have to use proofs or just use our intuition to solve the problems?
This is a good question. One thing we will see this semester is that our intuitions can sometimes be wrong, and horribly so. Therefore, mathematicians attempt to make their work as precise as possible. For HW problems for which it is relevant, I will expect proofs that, in plain English sentences, convince most readers of why they should believe such or such. On the first quiz I (implicitly) asked whether there are a finite number of prime numbers. Some people wrote that since there are infinite numbers, then there must also be an infinite number of prime numbers. This comes from intuition to some people, but how would you convince someone who does not share that intuition? You should always consult your intuition, since that is a very important guiding tool in mathematics, but also be very cautious lest it lead you astray. Mathematicians surprise themselves all the time to learn that something they had thought was obvious is in fact not even true.