Issuu

SOLUTIONS MANUAL Discrete Mathematics with Ducks 2nd Edition by Sarah Marie Belcastro Chapter 1

Counting and Proofs 1.2 Try This! Let’s Count 1. 2 + 6 + 1 + 1 = 10. 2. 3 · 5 = 15. 3. Six as there are five different ice-cream containers. 4. 5 · 5 · 5 = 125 orders because one might want all flavors the same. 5. This one is a pain, intentionally. First, 51 + 2 52 + 53 = 5+ 20+ 10 = 35 (the 2 52 is because it matters which flavor is ordered with 1 quart and which is ordered with 2 quarts), then just 5 4 4 4 4 = 10, then + + = 4 + 6 + 4 = 14 and = 4. Of course, students do not yet 3 1 2 3 3 know this notation, so they will likely write out solutions exhaustively and at length. 6. 3 + 2 + 1 = 6. 7. Three, as there are only two colors. To assure 7 monochromatic armbands, 13 armbands must be drawn (worst case: b-g-b-g-b-g-b-g-b-g-b-g-b/g). 8. 5 · 3 · 6 = 90. 9.

(a) n − 1.

(b) n − 1, then n − 2. (c) n − i.

(d) (n − 1) + (n − 2) + . . . 1 = n(n − 1)/2. 10.

(a) 3 · k.

(b) k + 1 as there are k containers. 11.

(a) The sum of their sizes. (b) The sum of their sizes! (c) Yes, the WEBS problem and the Frisbee tournament problems. (d) m + m + · · · + m = n · m.

12. m · k; yes, related to the ice-cream and snack-box problems. 2

1.9. Problems That Use Counting or Proofs

1.9 Problems That Use Counting or Proofs 1. 4 · 7 = 28. 2. 28 · 3 · 2 = 168. 3. An even number n can be written as 2k for some integer k. So, the sum of two even numbers is n1 + n2 = 2k1 + 2k2 = 2(k1 + k2 ) = 2k3 , which is even. 4. An odd number n can be written as 2k + 1 for some integer k. So, the sum of two odd numbers is n1 + n2 = 2k1 + 1 + 2k2 + 1 = 2k1 + 2k2 + 2 = 2(k1 + k2 + 1) = 2k3 , which is even. 5. 28 by the product principle using slots. 6. 5 · 4 + 3 · 3 = 29. 7. A binary number n that ends in 0 is the sum of some powers of 2, e.g., n = 2a + 2b + · · · + 2c where the lowest possible power of 2 is 21 = 2. Then we may write n = 2(2a−1 + 2b−1 + · · · + 2c−1 ) and so n is even. 8. An odd number n can be written as 2k + 1 for some integer k. To write n as a binary number, we must write it as a sum of powers of 2. This sum must have lowest power 0 (as in 20 ) or else every term of the sum will be divisible by 2. That means that the binary representation will end in a 1 = 20 . 9. There are 11 · 3 · 5 · k = 165k choices and 1,095 days, so k ≥ 6.63. But, of course, k must be an integer . . . so there are at least seven possible drinks. 10. Two consecutive perfect squares are n2 and (n + 1)2 . n2 − (n + 1)2 = n2 − n2 − 2n − 1 = −2n − 1 = −2n + 1 − 2 = 2(−n − 1) + 1, which is odd. 11. 11 = 10 + 1; and, 3 because there are only two different first digits (1, 2). 12. Counterexample: 32 + 42 = 25 is odd. 13. 15 · 8 = 120. 14. 15 · 6 = 90. 15. 5 + 6 + 3 + 4 = 18. 16. Nope. 2 + 3 = 5 is odd. (However, if we exclude 2, then the remaining primes are odd and so the sum of any two of them will be even.) 17. There are 1,440 minutes per day and so (1,440) · 23 = 960 90-second intervals. 1,042 > 960 so two flights must take off within the same interval. 18. Write n = 2k for some integer k. Then (−1)n = (−1)2k = ((−1)2 )k = 1k = 1. 19. 107 .

1. Counting and Proofs

20. 94 = 6561. 21. An odd number 2k + 1 times an odd number 2r + 1 is (2r + 1)(2k + 1) = 4kr + 2k + 2r + 1 = 2(2kr + k + r) + 1 and thus is odd. 22.

(a) Check 2,000,000 versus 220 = 1, 048, 576: not enough subsets. (b) By trial and error, see that 2,100,000 > 221 = 2,097,152 but 2,200,000 < 222 = 4,194,304.

23. For even n = 2k, 3(2k)3 + (2k) + 5 = 2(3 · 4k3 ) + 2k + 2 · 2 + 1 = 2(3 · 4k3 + k + 2) + 1, which is odd. For odd n = 2k + 1, 3(2k + 1)3 + (2k + 1) + 5 = odd + odd + odd = odd. 24. 99 · 2 + 1 = 199; 99 · 3 + 1 = 298; 99 · k + 1. 25. Green and brown socks: three for the first pair, then another two for the next pair, and so forth and so on, so 50 · 2 + 1 = 101.

Three colors of socks: four for the first pair, then another two for the second pair (using the leftover two socks), and so forth and so on: 50 · 2 + 2 = 102.

k colors of socks: k + 1 for the first pair, then another two for the second pair (using the leftover k − 1 socks), and so forth and so on: 50 · 2 + k − 1 = 99 + k.

26. All the usual primes are still prime, and 1 is also prime. If 1 were prime, we would no longer have unique factorization of natural numbers—for example, 6 = 2 · 3 = 2 · 1 · 1 · 1 · 3 = 1 · 2 · 3 . . . . 27. There are no prime numbers with this definition, because 1 is a positive divisor of every integer, and 1 is not included in this definition! It would be silly to have a class of numbers with no members. 28. There are 3 · 2 = 6 regular options plus 2 · 1 Fancy Tips, so 6 + 2 = 8. 29. By the pigeonhole principle, if each bin had only 13 skeins then you’d only have 104 miniskeins. 30.

(a) Note that the numbers 1–6, paired with the numbers 12–7, form six sums of 13. If no pair of the 7 numbers sums to 13, then all the numbers must be in one of these two subsets—but that’s only 6 numbers, so the seventh number must come from the other set and pair to make a sum of 13. (b) Similarly, the numbers 12–7, paired with the numbers 6–1, form differences of 6. The same argument applies. (c) Now we look at the numbers 1–3 with 4–6, and 7–9 with 10–12 to get six pairs with differences of 3. The same argument as above applies.

31. We have 7 numbers in the range 1–20. There are 27 = 128 possible subsets, and the highest possible sum is 14 + 15 + 16 + 17 + 18 + 19 + 20 = 119. So there are at most 119 different subset sums, and more subsets than that—thus, by the pigeonhole principle, there are two subsets that have the same sum.

1.9. Problems That Use Counting or Proofs

32. We can subdivide the square mile into four half-mile squares. By the pigeonhole principle, we know that two of the five Dunkin Donutses must be in the same half-mile square. The furthest these could be apart is the diagonal of the square, or √12 ≈ .71 < .75 miles apart. However, we could have four Dunkin Donutses at the corners of our square mile, and one in the center, and no two of these would be within half a mile of each other. 33. Well, only one at a time, but there are 2 + 2 · 6 + 2 + 1 + 3 = 20 shelves on which it might be found. And yes, the author does own this book. 34. 12 times 2 is 24. 35. If a(ab + 1) is odd, then both a and ab + 1 must be odd. Therefore a is odd, so a = 2k + 1. Now (2k + 1)b + 1 = 2kb + b + 1 is odd, which means that b + 1 is odd (because 2kb is even) and therefore b is even.

Chapter 2

Sets and Logic 2.4 Try This! Problems on Sets and Logic 1. 4; {0, / {0}, {cat}, {{dog}}, {{2.1, 6}}, {0, cat}, {0, {dog}}, {0, {2.1, 6}}, {cat, {dog}}, {cat, {2.1, 6}}, {{dog}, {2.1, 6}}, {0, cat, {dog}}, {0, cat, {2.1, 6}}, {0, {dog}, {2.1, 6}}, {cat, {dog}, {2.1, 6}}, {0, cat, {dog}, {2.1, 6}}}. (24 = 16.) 2. First logic-language it. For all times t, and for all people p, p can be fooled at time t. (There are certainly other possible interpretations.) The negation will be, There exists a time t and a person p such that p cannot be fooled at time t. 3. For example, −16, 8, 12, . . . . These are the even integers. 4.

(a) A ∪ B = A ∩ B; A ∩ B = A ∪ B.

(b)

P T T F F

Q T F T F

P∨Q T T T F

¬(P ∨ Q) F F F T

P T T F F

Q T F T F

¬P F F T T

¬Q F T F T

(¬P) ∧ (¬Q) F F F T

P T T F F

Q T F T F

P∧Q T F F F

¬(P ∧ Q) F T T T

P T T F F

Q T F T F

¬P F F T T

¬Q F T F T

(¬P) ∨ (¬Q) F T T T

(c)

2.6. Try This! A Tricky Conundrum

(d) Let x ∈ A ∪ B. Then x 6∈ (A ∪ B), so x 6∈ A and x 6∈ B, so x ∈ A ∩ B. Similarly, let x ∈ A ∩ B. Then x 6∈ A and x 6∈ B, so x 6∈ (A ∪ B). Therefore, x ∈ A ∪ B. Now let x ∈ A ∩ B. Then x 6∈ (A ∩ B), so x 6∈ A or x 6∈ B, so x ∈ A ∪ B. Similarly let x ∈ A ∪ B. Then x 6∈ A or x 6∈ B, so x 6∈ (A ∩ B). Therefore x ∈ A ∩ B. (e) Sure.

n [

Ai =

i=1

n \

Ai and

i=1

n \

Ai =

i=1

n [

Ai .

i=1

(f) Yes; ¬(P1 ∨ · · · ∨ Pn ) is logically equivalent to ¬P1 ∧ · · · ∧ ¬Pn , and ¬(P1 ∧ · · · ∧ Pn ) is logically equivalent to ¬P1 ∨ · · · ∨ ¬Pn. 5.

(a) {−10, −9, −8, −7, −6, −4, −2, 0, 2, 4, 6, 7, 8, 9, 10}.

(b) {−10, −9, −8, −7, 7, 8, 9, 10}. (c) A.

6. Check by truth table to see that the answer is “yes”:

P⇒Q T F T T

P T T F F

Q T F T F

n [

Ai = An ;

i=1

n \

i=0

¬(P ⇒ Q) F T F F

P T T F F

Q T F T F

¬Q F T F T

P ∧ ¬Q F T F F

Ai = {0}.

9. No; n + 5 has a different value for each n, so such an m cannot have a single value.

2.6 Try This! A Tricky Conundrum 1. Solutions will vary. 2. NA. 3.

(a) Let learn about sets be S, let learn about logic be L, and let go on to the next chapter be C. (b) C ⇒ (S ∨ L).

2. Sets and Logic

(d)

S∨L

C ⇒ (S ∨ L)

¬S ∧ ¬C

T T T T F F F F

T T F F T T F F

T F T F T F T F

T T T F T T T F

T T T F T T T T

F F F F F F T T

(C ⇒ (S ∨ L))∧ (¬S ∧ ¬C) F F F F F F T T

(C ⇒ (S ∨ L))∧ (¬S ∧ ¬C) ⇒ ¬L T T T T T T F T

4. Solutions will vary. 5.

(a) Use the contrapositive. If n is odd, then n = 2k + 1 and n3 + 6n2 − 2n = (2k + 1)3 + 6(2k + 1)2 − 2(2k + 1) = 2(4k3 + 6k2 + 3k + 3(2k + 1)2 − (2k + 1)) + 1, which is odd.

(b) Use the contrapositive. Suppose x < 0. Then x5 + 7x3 + 5x < 0 and x4 + x2 + 8 > 0, so x4 + x2 + 8 > x5 + 7x3 + 5x.

(c) Suppose for the sake of contradiction that it can be tiled with dominoes. Then it has an even number of squares. However, 65 is odd; contradiction. (d) Tile the right-most column with n−1 2 vertical dominoes. Then tile the left-most n − 1 columns of horizontal dominoes. columns with n−1 2

2.9 Bonus: Truth Tellers Puzzle1: The simplest way to do this problem is by reasoning. Examine the three cases where Rachel, Tess, or Nicol is the liar. If Rachel is the liar, Tess and Nicol are truthful. However, Nicol and Tess contradict each other because Tess claims ze was out of town whereas Nicol says zesaw Tess in town. Thus, Rachel is not the liar. If Tess is the liar, Rachel and Nicol are truthful. Rachel’s and Nicol’s statements are not really related, so this situation is consistent. If Nicol is the liar, then Rachel and Tess are truthful. However, Rachel and Tess contradict each other because Rachel says Tess knows Amy whereas Tess says ze doesn’t know Amy. Therefore, Tess is the liar.

M D M true D false (M says) ∧ (D says) T T T F F Puzzle2: T F TF / T F F FT / F F T F F FT / TF / F There is no way that the parental statements can be consistent. Project:

D T T F F

berries are safe T F T F

D says T F F T

2.9. Bonus: Truth Tellers

If duck says yes, that could result from the berries being safe or unsafe; the same is true if the duck says no. 2. This will give no information about berries . . . .

D T T F F

berries are safe T F T F

D∧ berries are safe T F FT / FT /

If duck says yes, that could result from the berries being safe or unsafe.

D T T F F

berries are safe T F T F

D∨ berries are safe T T TF / FT /

If duck says yes, that could result from the berries being safe or unsafe.

D T T F F

berries are safe T F T F

D ⇒ berries are safe T F /T F /T F

If duck says no, that could result from the berries being safe or unsafe. (If the duck says yes, we do learn that the berries are safe. However, we can’t depend on that answer.)

D T T F F

berries are safe T F T F

D ⇐ berries are safe T T /F T /T F

If duck says yes, that could result from the berries being safe or unsafe. 7. Again, this tells us nothing about berries. We need to design a question that will produce answers that are consistent with the safety of the berries. Here are four questions that work: Would a duck who answers oppositely from you say that the berries are edible? Do you tell the truth if and only if the berries are edible? Is it true that (if the berries are safe, then you tell the truth) and (if the berries are safe, then you lie)?

2. Sets and Logic

If I asked you whether the berries are safe, what would you say? D T We give a truth table for this last question: T F F

berries are safe T F T F

D says T F /F T /T F

2.12 Problems about Sets and Logic 1. {2}. 2. The question is asking about non-urgent care. It excludes dental care and hospital care and urgent care. The question could have been worded, “In the last 12 months, how often did you get a prompt appointment for non-urgent health care at a doctor’s office or clinic?” 3. Here they are: (doctor or health provider), (discuss or provide), (methods and strategies), (smoking or using). All three of the ors are meant mathematically, but the and is used to mean union instead of intersection. 4. These are the negative integers {−9, . . . , −1}, so the cardinality of the set is 9.

P T T F F

Q T F T F

¬P ∨ Q T F T T

P ∧ (¬P ∨ Q) T F F F

6. {2n | n ∈ W} or {n | n = 2k , k ∈ W}.

(a) {(2, 2), (2, 3), (3, 2), (3, 3)}.

(b) {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (2, 4), (3, 4), (4, 4), (4, 3), (4, 2)}. (c) {(1, 1), (2, 1), (3, 1)}.

2.12. Problems about Sets and Logic

P T T F F

Q T F T F

¬P F F T T

¬Q F T F T

P⇒Q T F T T

¬Q ⇒ ¬P T F T T

10.

P T T F F

Q T F T F

¬P F F T T

¬Q F T F T

Q⇒P T T F T

¬P ⇒ ¬Q T T F T

11. Let A = {1, 2, 3} and B = {2, 3, 4}. 12. This is total nonsense. The moon is not made of green cheese. Even if Moscow had existed as a city in the time of Aristotle, he certainly was not and is not its President. Every fiber of your being is probably screaming “False, False, FALSE!” But think again. Because the moon is not made of green cheese, it doesn’t matter what the statement is claiming this implies; the implication holds anyway, because a false statement implies, well, everything. See the appropriate truth table.

13.

14. Let A,C be disjoint. For example, let A = {1, 2},C = {3}, B = {4}, D = {5}. Then (A × B) ∪ (C ×D) = {(1, 4), (2, 4), (3, 5)} but (A∪C)×(B∪D) = {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}. 15. Use the contrapositive. Let B = 0. / Then A \ B = A \ 0/ = A, which is not equal to 0/ unless A = 0. / 16. Use a truth table and trace backwards. We will have one value for R but two possibilities each for P, Q, S, so we have eight rows. P T T T T F F F F

Q T T F F T T F F

S T F T F T F T F

R F F F F F F F F

P⇒Q T T F F T T T T

R∧S F F F F F F F F

(P ⇒ Q) ⇔ (R ∧ S) F F T T F F F F

2. Sets and Logic

We see that (P ⇒ Q) ⇔ (R ∧ S) is true when P, S are true and Q is false, or when P is true and Q, S are false. Thus, we conclude that P is true and Q is false. 17. In math-logic language, this expression is (c > 5 ∧ b = a) ∨ c ≥ 5. The crucial point is to notice that (c ≥ 5) is logically equivalent to (c > 5) ∨ (c = 5). So let c > 5 be P, let b = a be Q, and let c = 5 be R. P T T T T F F F F

Q T T F F T T F F

R T F T F T F T F

P∧Q T T F F F F F F

P∨R T T T T T F T F

(P ∧ Q) ∨ (P ∨ R) T T T T T F T F

Now notice that P ∨ R would have the same truth table. Thus, we can rewrite this as c ≥ 5. 18. For every k that is a multiple of 3, there is a subset of the natural numbers with cardinality k. It’s not true because k could be negative, but no set has negative cardinality. The negation is ∃k ∈ 3Z, such that ∀S ⊆ N, |S| = 6 k. In English, that says there is a k evenly divisible by 3 such that no subset of N has cardinality k. And that’s true, because we can take k = −63. 19. This is a biconditional, so do it in two parts. (⇒) Direct proof. Suppose n is odd, so n = 2k + 1. Then n2 = (2k + 1)2 = 2(2k2 + 2k) + 1, which is odd. (⇐) Use the contrapositive. Suppose n2 is even, so n2 = 2k. Because n2 = n · n, we see that k = n·n 2 ; and because k is an integer, n must be divisile by 2 and so is even. 20. Here goes some double-inclusion provin’: Consider x ∈ {3k | k ∈ Z}; because k ∈ Z, then 3k ∈ Z so x ∈ Z. Similarly, we see that for y ∈ {3k + 1 | k ∈ Z}, y ∈ Z and for z ∈ {3k + 2 | k ∈ Z}, z ∈ Z. Now consider ℓ ∈ Z. If ℓ is divisible by 3, then ℓ ∈ {3k | k ∈ Z}. Otherwise, divide ℓ by 3; the remainder must be 1 or 2 (as if it were 0, ℓ would be divisible by 3). If the remainder is 1, then ℓ ∈ {3k + 1 | k ∈ Z}, and if the remainder is 2, then ℓ ∈ {3k + 2 | k ∈ Z}. Therefore, ℓ ∈ {3k | k ∈ Z} ∪ {3k + 1 | k ∈ Z} ∪ {3k + 2 | k ∈ Z}. 21. Suppose there are only finitely many primes. List these k primes, p1 , p2 , . . . , pk . Multiply them all together to get a number larger than any of the primes, and add 1. It’s not divisible by any known prime (as otherwise 1 would also be divisible by that prime), so it is prime itself. This is a contradiction, because there are now k + 1 primes. 22. The binary representation of a natural number is a sum of powers of two, so notice that n is divisible by 4 exactly when (binary representation of n) = 22 ( sum of some powers of 2). In other words, the binary representation must end in 00. The contrapositive of the original statement is n ∈ N is divisible by 4 if and only if the binary representation of n ends in 00.

2.12. Problems about Sets and Logic

23.

P T T F F

Q T F T F

¬P F F T T

¬P ∨ Q T F T T

24. Example 1.5.4, Example 1.5.5. 25. In logic language, the statement says, If you own a boat, then you wash it after each use. If you don’t own a boat, then you wash your non-boat every time you use it. The truth table for implies says that if the hypothesis is false, then the statement as a whole is true, which is the case here. 26.

(a) 3. (b) 4. (c) 1.

27.

(a) (2, 5), (−3, 1), (0, 1). (b) 4. (c) 0/ because no element of A has a 0 in the right-hand position.

28.

(a) {1, 6, 7, 8, 9, 10}.

(b) B \C = {5, 7}; (B \C) \ A = {7}.

29. x is not prime and x ≥ 52.

30.

p T T F F

q T F T F

¬p F F T T

¬q F T F T

((¬p) ∧ q) F F T F

(p ∨ (¬q)) F T F F

((¬p) ∧ q) ∧ (p ∨ (¬q)) F F F F

x−y ∈ Z. Thus the negation is ∃ x, y ∈ Z such 31. In logic notation, this statement is ∀ x, y ∈ Z, 5 x−y x−y that 6∈ Z. This reads as There exist integers x and y such that is not an integer. 5 5 32.

(a) 6 ∃ k ∈ N such that 2|k ∧ k is prime.

(b) 6 ∃ △ such that △ has four sides. (c) 6 ∃ a, b ∈ Z such that a2 /b2 = 2.

(d) 6 ∃ k ∈ N such that (∃ m ∈ Z such that m2 = k) ∧ (k = p + 1) for p a prime. 33. If y does not have a sister, then x2 < 100. 34. See solutions to Section 2.4 Problem 4.

2. Sets and Logic

35. See solutions to Section 2.4 Problem 4. 36.

(a) If n is even, then n = 2k. Therefore n − 1 = 2k − 1 = 2(k − 1) + 1, which is odd. (b) Suppose n − 1 is not odd. Then n − 1 is even, so n − 1 = 2k and thus n = 2k + 1, which is odd. . . and therefore n is not even. (c) Suppose n is even but n − 1 is not odd. Then n − 1 is even, so n − 1 = 2k and thus n = 2k + 1, which is odd. . . contradiction!

37. Suppose x is even. Then x − 2k. Therefore, 4x2 − 3x + 1 = 4(2k)2 − 3(2k) + 1 = 16k2 − 6k + 1 = 2(8k2 − 3k) + 1 is odd.

Now suppose 4x2 − 3x + 1 is odd. Then 4x2 − 3x + 1 = 2k + 1, so 4x2 − 3x = 2k. Factoring, we have x(4x − 3) = 2k. Thus either x is even or 4x − 3 is even. Note that 4x − 3 = 2(2x − 2) + 1 is odd and thus cannot be even, so x must be even.

38. Let’s do this in stages. • If an organization (is primarily religious in purpose and falls under the regulations 940 CMR 2.00) or (does not raise or receive contributions from the public in excess of $5,000 during a calendar year or does not receive contributions from more than ten persons during a calendar year, if all of their functions, including fundraising activities, are performed by persons who are not paid for their services and if no part of their assets or income inures to the benefit of, or is paid to, any officer or members) then it is not required to have a “Certificate of Solicitation.” • If an organization ((is primarily religious in purpose) and (falls under the regulations 940 CMR 2.00)) or ((does not raise or receive contributions from the public in excess of $5,000 during a calendar year or does not receive contributions from more than ten persons during a calendar year), if all of their functions, including fundraising activities, are performed by persons who are not paid for their services and if no part of their assets or income inures to the benefit of, or is paid to, any officer or members) then it is not required to have a “Certificate of Solicitation.” • If an organization ((is primarily religious in purpose) and (falls under the regulations 940 CMR 2.00)) or (if all of their functions, including fundraising activities, are performed by persons who are not paid for their services and if no part of their assets or income inures to the benefit of, or is paid to, any officer or members and (does not raise or receive contributions from the public in excess of $5,000 during a calendar year or does not receive contributions from more than ten persons during a calendar year)) then it is not required to have a “Certificate of Solicitation.” • If an organization ((is primarily religious in purpose) and (falls under the regulations 940 CMR 2.00)) or (if (all organizational or fundraising functions are performed by unpaid persons) and (no part of their assets or income inures to the benefit of, or is paid to, any officer or members) and (does not raise or receive contributions from the public in excess of $5,000 during a calendar year or does not receive contributions from more than ten persons during a calendar year)) then it is not required to have a “Certificate of Solicitation.” • If an organization ((is primarily religious in purpose) and (falls under the regulations 940 CMR 2.00)) or (if (all organizational or fundraising functions are performed by unpaid persons) and (no part of organizational assets or income benefits any officer or members) and

2.12. Problems about Sets and Logic

((does not collect contributions from the public in excess of $5,000 during a calendar year) or (does not receive contributions from more than ten persons during a calendar year))) then it is not required to have a “Certificate of Solicitation.” • If an organization ((is religious) and (falls under 940 CMR 2.00)) or (if (no one is paid for organizational work) and (neither officers nor members benefit from organizational assets or income) and ((public contributions are < $5, 000 during a calendar year) or (contributions are from ≤ 10 persons during a calendar year))) then it is not required to have a “Certificate of Solicitation.” 39. {x ∈ Z | x is divisible by 4} or {4x | x ∈ Z}. 40. Because A ∩ B ⊂ B, by definition (A ∩ B) ∩ (A \ B) = 0. / Therefore they cannot be equal unless both A ∩ B and A \ B are empty. That’s only true if A is the empty set.

Chapter 3

Graphs and Functions 3.3 Try This! Play with Functions and Graphs 3.3.1 Play with Functions 1. f3 (a) = c, f3 (b) = c; f4 (a) = d, f4 (b) = c; f5 (a) = e, f5 (b) = e; f6 (a) = d, f6 (b) = e; f7 (a) = e, f7 (b) = d; f8 (a) = c, f8 (b) = e; f9 (a) = e, f9 (b) = c. Nine. 2. 23 = 8. 3. 102 = 100. 4. 210 = 1024. 5. For each of those m elements, there are q choices of target element. Thus, qm .

3.3.2 Play with Graphs 1. Solutions will vary. 2. The degrees are 2, 3, 3, 2, 2, 4 with sum 16. There are 8 edges. The total degree is twice the number of edges. 3. The total degree is twice the number of edges. Proof: Think of the degree as counting the number of edges at each vertex. In this way, every edge is counted exactly twice, once for each incident vertex. 4. For the graphs in Figure 3.3 on page 73, the number of odd vertices is four, six, and two, respectively. All are even. Conjecture: The number of odd vertices is always even. Proof (by contradiction): Suppose not. Then the total degree involves an odd number of odds and so will be odd, which contradicts the proof from the previous problem.

3.3.3 A Dot Game 1. For five vertices, there can be a draw. For six vertices, there must always be a winner and loser. See the argument given in Section 3.9. 2. See previous answer. 3. If you start with fewer vertices, then there can be a draw. If you start with more vertices, you must have a winner and a loser (use the same argument as for six vertices).

3.8. Try This! More Graph Problems

3.8 Try This! More Graph Problems 1. Wn contains a cycle of size n− 1, which contributes n− 1 edges. Then, there is an edge joining the nth vertex to each of the other n − 1 vertices; this contributes another n − 1 vertices for a total of 2n − 2 edges. 2. No. The left-hand graph has no vertices of degree 2, but the right-hand graph has one of them. 3. Well, Kv has

v(v − 1) v(v − 1) edges, so G has − e edges. 2 2

4. The complement of C5 is the star inside K5 , which unravels to make another C5 . If a graph is isomorphic to its complement, then v(v−1) − e = e, which is equivalent to v(v−1) = 2e and 2 2 to v(v − 1) = 4e. Also, a cycle graph has the same number of vertices as edges, so 4e = 4v. Thus, v − 1 = 4 and we must have v = 5. 5. They are isomorphic; move the center and upper vertices over to the right, and then move the leftmost vertex upwards. To exhibit an isomorphism, the graphs must be labeled first and labelings will vary from person to person. 6. The seven nonisomorphic subgraphs of K3 are shown in a row . . .

. . . above the 17 distinct subgraphs of K3 . 7. The two left-hand graphs are isomorphic; the top and bottom pairs of vertices of the octagonal graph can be squished inwards to form the inner square of the cube graph. The right-hand graph is also isomorphic to the other two; the leftmost and rightmost vertices can be untangled to form the outer square of the cube graph, and the remaining four vertices can be untangled to form the inner square of the cube graph. To exhibit an isomorphism, the graphs must be labeled first and labelings will vary from person to person. 8. No. The left-hand graph has two disjoint 3-cycles, but the right-hand graph has two incident 3-cycles.