Math 213 Discrete Mathematics Homework Problems

Below are listed the required homework problems for each section.

Note: If a problem listed here has multiple parts but no parts are listed here, then all parts are assigned.

You should also complete the "Test Yourself" questions for every section that we cover. The answers are after the normal exercises (try to answer without looking first). You do not need to turn in your answers to "Test Yourself" questions.

Note that some problems have complete or partial solutions in your book:

You will notice that a great many of the problems are blue. You should make a true, honest attempt at completing these problems before checking the book. Then, compare your answer to the book. Do not hesitate to ask if you are unsure why your answer is different than the book's answer. Problems with full solutions in the book will be graded only for completion, so it is your responsibility to check whether your answer is correct and whether you understand the solution. Of course, if you are not sure, then you should ask.

Chapter 1
1.1:  1, 3, 7abcd, 8, 11.
1.2:  1, 2abcd, 3, 4, 7cd, 8abcd, 9abcdefghij, 11ad.
1.3:  1, 7, 13, 15abcde.

Chapter 2
2.1:  3, 5abcd, 6, 8abcde, 9abc, 12, 14, 17, 23, 25, 28, 32, 41, 45#.
2.2:  4, 5, 6, 7, 13a, 20abcdefg, (22, 23)%, 26, 29, 34, 40, 42, 46abcdef, 47.
2.3:  3, 6, 7, 12ab, 18, 21, 22, 24, 25, 26, 29, 37, 38abcd, 40.

Chapter 3
3.1:  2, 4abcd, 6abc, 11, 13, 14, 15a, 18abcde, 19, 23ab, 24ab, 25ce, 26ab, 27abcd, 30abc.
3.2:  1, 3ac, 4ac, 9, 10, 11, 13, 15abcde, 16, 18, 20, 26, 28, 30, 38.
3.3:  2ab, 4abc, 5, 7, 9ab, 10abcdef, 11abcdef, 12ab, 13, 14, 21abde, 31, 32, 35, 36, 38, (46, 48, 53)%.
3.4:  1abc, 2, 3, 5, (7, 8, 10, 14, 19abcd)%, 21, 22, 24, 25, 33.

Chapter 4
4.1:  1, 3, 7, 8, 14, 15, 21, 27, 28, 30, 31.
4.2:  1, 4, 6, 12, 15, 16, 17, 19, (20, 22, 23, 24, 38)#.
4.3:  4, 6, 9, 12, 13, 15, 18, 21, 22, 24%, 35, 36, 37, 38%.
4.4:  2, 4, 6, 8, 12, 14, 15, 19, 21, 24, 25, 28, 36abcd, 37abc, 38abcd, 44%.
4.5:  1, 3, 5, 7, 9, 16, 17, 20, 23, 27, 29, 35.
4.7:  1, 3, 5, 8, 10, 11, 13ab, 20, 21, 23, 28%, 29%, 31abc, 32abcd%, 33, 34abcd%.
4.8:  1, 3, 5, (6, 8, 9, 10, 14)#19a, 21, 24.

Chapter 5
5.1:  1, 3, 11, 12, 13, 18abcde, 19, 20, 27, 37, 42, 43, 45, 53, 58, 59, 61, 62, 66, 71, 76.
5.2:  2, 3abcd, 5, 6, 8, 10, 12, 17, 20, 25, (36, 38)%.
5.3:  4, 6, 8, 12, 19, 24, 34ab, 45, 46.
5.4:  1, 5, 13, 25, 26, 27#, 31%.
5.6:  1, 3, 5, 11, 13, 17abc, 22abc, 25abc, 26, 39, 40.
5.7:  1ab, 2abc, 3, 5, 8, 12, 16, (18, 21)#, 28, 30, 33, 37, 41.
5.8:  1, 3ab, 5, (8, 9)%, 11, 13, 15, 16, 18, 22.

Chapter 6
6.1:  3ab, 5, 8abcd, 9abc, 10abcdefgh, 11, 16abc, 17abcdef, 18abcd, 19, 21, 22, 27abcde, 30, 31, 34ab.
6.2:  2ab, 5, 6, 8, 10, 16, 19, 23, 24, 25, 27, 28, 30, 33.
6.3:  1, 3, 5, 6, 7, 9, 22ab, 23, 27, 28, 30, 31, 34, 41, 44.
6.4:  17, 18, 19, 25, 26, 27.

Chapter 7
7.1:  1, 3abcd, 7abcd, 11abcd, 17abcde, 18abcdefg, 19, 33, 39, 40, 41, 43, 45.
7.2:  1, 2ab, 3, 5, 7ab, 8, 10, 11ab, 13a, 14, 15, 16, 28, 3646, 47, 52#.
7.3:  1, 3, 12, 19, 20, 21, 22, 26.
7.4:  1, 3, 7a, 8, 10, 11.

Chapter 8
8.1:  1ab, 2, 3abcde, 6abc, 7abcd, (13, 15, 16)%.
8.2:  1, 3, 6, (9, 11, 12, 15, 27, 31)%, 34, 40, 43, 45, 48, 51.
8.3:  2a, 3, 5, 7, 11, 15abcd, 16ab, (19a, 21, 22, 25)%, 36, 38, 41, 45.

Chapter 9
9.1:  3, 5, 8, 9, 12ab, 18, 21, 22, 28, 31.
9.2:  6, 8, 9, 13abc, 14abcd, 16, 18a, 21, 32, 35, 37abcd, 39abcd, 41.
9.3:  4, 6, 11, 13, 16, 19, 23abc, 31, 33abcdef, 35.
9.4:  1, 3, 5, 7, 10, 12, 20, 25, 26, 29, 31.
9.5:  1, 5abcdefg, 6, 8, 11cdef, 13abd, 15, 18%, 19, 22, 23, 30.
9.6:  2ab, 3, 5, 10, 11, 14, 16%, 17, 19.
9.7:  3, 5, 6, 9, 11, 16, 19, 23, 29, 31, 36, 39, 43, 47, 52.

Chapter 10
1.4:  1, 3, 5, 8, 12.
4.9:  1, 3, 5, 6, 12, 16ab, 17, 23abcdef, 24.
10.1:  1, 4, 8abcd, 9abc, 11, 12, 13, 14, 19, 20, 29, 30.
10.4:  3, 8, 9, 10, 11, 12, 13, 14, 17, 22, 23, 25.

Problems marked with % have a note below:
2.2 #22, 23:  Parts a, d, f of these problems are in the back of the book and will be treated as blue problems.
3.3 #46, 48, 53:  Do not worry about "formal logical notation." Just write each statement and its negation using quantifiers and then determine which is true (and justify your answer).
3.4 #7, 8, 10, 14, 19:  You do not need to draw diagrams to justify your answers to these problems. Just state which rule of inference or logical fallacy the argument exhibits.
4.3 #24:  They mean that you should prove the given statement using the listed theorems and exercises as "previously known results" that you are allowed to assume are true.
4.3 #38:  There is a typo at the end. They write r - s when they mean r + s. That is not the mistake that you are looking for.
4.4 #44:  Problems 44-50 are very interesting (but difficult) problems. You should read them all and attempt a few of them (though only 44 will be graded).
4.7 #28, 29:  You need to prove it in two ways: a. by contrapositive and b. by contradiction.
4.7 #32, 34:  You may use a calculator to approximate the square roots.
5.2 #36, 38:  The mistake in these proofs is not that they are incomplete. The part that is shown has an error, which you are meant to find.
5.4 #31:  They are talking about the existence part of the proof. They are asking you to pick two numbers for k: one where k +1 is even, and one where it is odd. In each case, find the binary representation for the smaller number (k/2 or (k+1)/2, depending on the case) and show how multiplying by 2 (and adding 1 in one case) leads to the binary representation for k + 1. Choose k to be at least 42.
5.8 #8, 9:  The solution given by the book finds the characteristic equation from scratch. You do not have to do this. Just start with the usual formula for the characteristic equation.
8.1 #13-16:  The "directed graph" of a relation is just the arrow diagram with only one copy of the set drawn.
8.2 #9-31:  The instructions for these problems are before Problem 9.
8.3 #19-31:  The instructions for these problems are before Problem 19.
9.5 #18:  They do not mean that you must make the arrangement "MIIIISSSSPP." They mean that first you will select a slot for the M, then 4 slots for the I's,  then 4 slots for the S's, and finally the last two slots for the P's.
9.6 #16:  The book has a solution to 16b, but they have a small mistake. Everything is correct until the paragraph that begins "To find N(R≥6 ∩ L≥7)..." The argument should instead say something like this: "To find N(R≥6 ∩ L≥7), we count the number of selections that contain both at least 6 root beers and at least 7 lemonades. The other 2 cans can be any of the 5 flavors (including root beer and lemonade again), so we are choosing 2 from 5 with repetition allowed. The number of ways to do this is ((2+5-1) choose 2) = (6 choose 2) = 15)." The rest of the proof uses the correct logic, but uses their incorrect value of 9 for N(R≥6 ∩ L≥7) instead of the correct value 15. So the final two calculations should end: "...= 715 + 495 - 15 = 1,195" and "...= 3,876 - 1,195 = 2,681." (Differences from the book are bold.) So the correct final answer is 2,681.

Problems marked with # have a hint below:
2.1 #45:  Try first writing the statements in statement form by assigning statement variables to each of their parts (for example, let r be the statement that Ann is a math major, and so on).
4.2: #20, 22, 23, 24, 38:  Many of these are false. All you need to do to prove they are false is find a counterexample.
4.8: #6, 8, 9, 10, 14:  Many of these are false. All you need to do to prove they are false is find a counterexample.
5.4 #27:  Try a proof by contradiction: Suppose some positive integers greater than 1 are neither prime nor a product of primes. Let S be the set of all such integers. What does Well-Ordering say about S? Use that fact to find a contradiction.
5.7 #18, 21:  See the lecture notes for a hint on these proofs.
7.2 #52:  You have already shown that the function is one-to-one. What else do you need to show?