Discrete Mathematics, Solutions to Homework 1

Solutions to Homework 1 Discrete Mathematics 1. [1 #4] (a) 1a 2b 3c 2c 3a 1b (b) 3b 1c 2a 1a 2b 3c 4d 2d 1c 4b 3a 3b 4a 1d 2c 4c 3d 2a 1b 2. [1 #11] 3. [1 #12] (a) Not possible. Suppose without lost of generality that the Calculus test is offered the first available time. Since Calculus has common students with all other classes then Physics, History, and English must have their exam the second available time. This is not possible since Physics and History have common students. (c) Not possible. Note that any two of the following four classes share students: Calculus, Economics, Physics, and History. Then no two of these four classes can have their exam at the same time. So we need to have at least four different available exam times. (b) Day 1 Calculus Day 2 Physics English Day 3 History (d) Day 1 Calculus Day 2 Physics English Day 3 History Day 4 Economics 4. [2.1 #1] Yes. There are 263 = 17, 576 possible different initials. Since there are more residents (20, 000) than initials (17, 576) then there must be at least two residents with the same initials. 5. [2.1 #2] The number of possible codewords is 263 · 103 = 17 576 000. Since there are only 5000 books, there are more than enough codewords. 6. [2.1 #6] An m × n matrix has exactly mn entries. We have two possible values (0 and 1) per entry. So there are 2mn possible matrices. 7. [2.1 #8] There are 106 nonnegative integers (from 0 to 999 999). We can see all these numbers as 6-digit numbers if we allow leading zeros (from 000 000 to 999 999). From these, there are 96 numbers that do not contain the digit 2. So there are exactly 106 − 96 = 468 559 nonnegative integers less than 1 million that contain the digit 2. 8. [2.2 #2] 8 · 7 + 8 · 12 + 7 · 12 (A scientist and a psychic, OR a scientist and a cleric, OR a psychic and a cleric.) 9. [2.2 #3] 55 + 45 (All digits odd + all digits even.) 10. [2.2 #5] 1 · 264 + 255 (Start with d +do not have the letter d.) 11. [2.2 #6] 2 + 3 (Because 3 = 1 + 2 = 2 + 1 and 4 = 1 + 3 = 2 + 2 = 3 + 1.) 12. [2.3 #1] (a) 123, 132, 213, 231, 312, 321 1 (b) 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321. 13. [2.3 #4] √ ¡ 4 ¢4 8π e = 23.506 √ ¡ ¢6 (b) 6! = 720 and 12π 6e = 710.08 √ ¡ ¢8 (c) 8! = 40 320 and 16π 8e = 39 902. (a) 4! = 24 and 14. [2.3 #5] 2 · 3 · 2 · 1 = 12 15. [2.3 #6] (a) 4 · 1 · 3 · 2 · 1 = 24 (b) (n − 2) · 1 · 1 · (n − 3)! = (n − 2)! (Any number between 3 and n · the number 2 · the number 3 · the remaining n − 3 numbers in any order.) 16. [2.3 #7] 1 · 3 · 2 · 1 · 1 = 6 (The tallest · the middle 3 in any order · the shortest.) 17. [2.4 #5] The cost matrix is All possible routes and their costs are: ⎛ ⎞ − 1 8 11 ⎜ 16 − 3 6 ⎟ ⎜ ⎟ ⎝ 4 9 − 11 ⎠ . 8 3 2 − route 1 → 2 → 3 → 4 → 1, cost 1 + 3 + 11 + 8 = 23 route 1 → 2 → 4 → 3 → 1, cost 1 + 6 + 2 + 4 = 13 route 1 → 3 → 2 → 4 → 1, cost 8 + 9 + 6 + 8 = 31 route 1 → 3 → 4 → 2 → 1, cost 8 + 11 + 3 + 16 = 38 route 1 → 4 → 2 → 3 → 1, cost 11 + 3 + 3 + 4 = 21 route 1 → 4 → 3 → 2 → 1, cost 11 + 2 + 9 + 16 = 38 So the cheapest route is 1 → 2 → 4 → 3 → 1. 18. [2.5 #1] (a) P (3, 2) = 3 5! (b) P (5, 3) = = 5 · 4 · 3 = 60 2! 8! (c) P (8, 5) = = 8 · 7 · 6 · 5 · 4 = 6720 3! (d) P (1, 3) = 0 19. [2.5 #3] (a) 84 = P R (8, 4) 8! (b) 8 · 7 · 6 · 5 = = P (8, 4) 4! (c) 1 · 8 · 8 · 8 = 1 · P R (8, 3) (d) 1 · 6 · 5 · 1 = 1 · P (6, 2) · 1 2 20. [2.5 #4] 20 · 19 · 18 · 17 · 16 = 20! = P (20, 5) (All candidates must be different.) (20 − 5)! 21. [2.5 #6] 403 (There are 40 possibilities to stop each time. Here we are allowing full turns, that is, from a given number all around to itself.) 22. [2.6 #2] 235 − 1 (Not having a subscription is not an allowed possibility.) 23. [2.6 #5] 210 (All subsets except the empty set.) 24. [2.6 #6] 28 − 8 − 1 (All subsets except the 1-element subsets and the empty set.) 3