Page 1 of 6 B (The World of Mathematics) November 0, 006 Final Exam 006 Division: ID#: Name: 1. p, q, r (Let p, q, r are propositions. ) (a) (Decide whether the following holds by completing the truth table below. And write your conclusion with reason.) p (q r) (p ( r)) q. p q r p (q r) (p ( r)) q T T T T T F T F T T F F F T T F T F F F T F F F [ (Conclusion and reason)] (b) p (q r) (Express p (q r) using, and parentheses. Do not use or.) Points 1.. 3. 4. 5. 6. 7. 8. 9. 10.
Page of 6. (Find the following and explain your reasoning.) (a) 50 (50 teams are in a tournament. If there is no draw, how many games are required to decide the winner of the touranment? Why?) (b) 1000 A, B, C, D, E 5 100 5 n C m (How many ways are there to make 1000 paper cranes by five people, A, B, C, D, E, if each one makes at least 100? Use n C m to express your answer.) 3. 1 (Find the minimum cost of a connected network using the diagram below. Draw your network on the right as well by connecting corresponding points.) 3 3 5 5 4 3 3 5 3 3 1 4 1 3 4 3 3 3 5 1 3 (Total)
Page 3 of 6 4. 8 8 (An 8 8 chess board has checkered pattern in black and white.) (a) 1 (Show that it is impossible to cover all squares of the board except the top right and the bottom left corners by 1 rectangular plates without overlapping.) (b) 4 1 (Show the following. If we choose two white squares and two black squares properly, it is impossible to cover the rest of the board by 1 rectangular plates without overlapping.) 5. K 3,3 (Show that K 3,3 below is not a planar graph.)
Page 4 of 6 6. A A 0 A (Ms. A attended a party. There were 0 people including Ms. A. After some period, Ms. A asked the attendants how many people they shook hands with. All of them answered different numbers, and none of them shook hands with all. ) (a) A (Explain that Ms. A shook hands with at least one of them.) (b) 18 17 (Explain that there is a person who shook hands with exactly two persons, and they are the ones who shook hands with exactly 18 and 17 people.) 7. (Show that the graph below is not a Hamilton graph.)
Page 5 of 6 8. Γ = (X, E) v e (Let Γ = (X, E) be a tree with v vertices and e edges.) (a) v 1 (Show that if v, there is a vertex of degree 1.) (b) e = v 1 (Show by Mathematical Induction that e = v 1.) 9. 3 4 6 4 m v e f (Γ is a connected plane graph such that each vertex is of degree 3 and each face is surrounded by either four edges or six edges. Suppose there are m faces surrounded by four edges, and Γ has v vertices, e edges and f faces.) (a) 3f = e + m (Show that 3f = e + m.) (b) m (Determine m. Show work!)
Page 6 of 6 10. B 77 1 13 77 (Mr. B played games 77 consecutive days. Suppose he played at least one game each day but the total number of games is at most 13. Show that there is a certain consecutive period he played exactly 77 games. By a certain consecutive period, we mean for example, from the 3rd day to the 57th day.) If you wish, write Do Not Post. 1.. (a) (b) (c) 3.
Page 1 of 6 B (The World of Mathematics) November 0, 006 Solutions to Final Exam 006 1. p, q, r (Let p, q, r are propositions. ) (a) (Decide whether the following holds by completing the truth table below. And write your conclusion with reason.) p (q r) (p ( r)) q. p q r p (q r) (p ( r)) q T T T T T F T T T F T T T T T F T T T F T T F F F F T F F T T T T F T F T F T T F T F F T T T F T F F F T F F T [ (Conclusion and reason)] (b) p (q r) (Express p (q r) using, and parentheses. Do not use or.) p (q r) (p ( r)) q (p ( r)) q ((p ( r)) ( q)). F T T F T p T, q F, r F (p ( q) ( r))
Page of 6. (Find the following and explain your reasoning.) (a) 50 (50 teams are in a tournament. If there is no draw, how many games are required to decide the winner of the touranment? Why?) 1 1 49 49 49 (b) 1000 A, B, C, D, E 5 100 5 n C m (How many ways are there to make 1000 paper cranes by five people, A, B, C, D, E, if each one makes at least 100? Use n C m to express your answer.) 99 1000 99 5 = 505 5 505 5 504C 4 3. 1 (Find the minimum cost of a connected network using the diagram below. Draw your network on the right as well by connecting corresponding points.) 3 3 5 5 4 3 3 5 3 3 1 4 1 3 4 3 3 3 5 1 3 (Total) 1 ( )
Page 3 of 6 4. 8 8 (An 8 8 chess board has checkered pattern in black and white.) (a) 1 (Show that it is impossible to cover all squares of the board except the top right and the bottom left corners by 1 rectangular plates without overlapping.) 30 3 1 1 1 (b) 4 1 (Show the following. If we choose two white squares and two black squares properly, it is impossible to cover the rest of the board by 1 rectangular plates without overlapping.) 5. K 3,3 (Show that K 3,3 below is not a planar graph.) v = 6 e = 9 v e + f = f = e v + = 9 6 + = 5 5 n 1, n, n 3, n 4, n 5 3 n 1 4, n 4, n 3 4, n 4 4, n 5 4 Proposition 8. (ii) 18 = e = n 1 + n + n 3 + n 4 + n 5 4 + 4 + 4 + 4 + 4 = 0.
Page 4 of 6 6. A A 0 A (Ms. A attended a party. There were 0 people including Ms. A. After some period, Ms. A asked the attendants how many people they shook hands with. All of them answered different numbers, and none of them shook hands with all. ) (a) A (Explain that Ms. A shook hands with at least one of them.) 19 18 0 19 A 19 A... 17 18 18 A A A A (b) 18 17 (Explain that there is a person who shook hands with exactly two persons, and they are the ones who shook hands with exactly 18 and 17 people.) A 18 18 1 17 A 18 17 A 17 A 7. (Show that the graph below is not a Hamilton graph.) 3 5 6 6 Theorem 7.3. 5 6 Bipartite
Page 5 of 6 8. Γ = (X, E) v e (Let Γ = (X, E) be a tree with v vertices and e edges.) (a) v 1 (Show that if v, there is a vertex of degree 1.) x 1 x x 3 x 1 x 3, x x 4,... 1 (b) e = v 1 (Show by Mathematical Induction that e = v 1.) v v = 1 e = 0 e = v 1 v = k v 1 v = k + 1 v (a) 1 v 1 = k e e 1 Γ Γ k e 1 k 1 e = k = v 1 v = k + 1 v v v 1 9. 3 4 6 4 m v e f (Γ is a connected plane graph such that each vertex is of degree 3 and each face is surrounded by either four edges or six edges. Suppose there are m faces surrounded by four edges, and Γ has v vertices, e edges and f faces.) (a) 3f = e + m (Show that 3f = e + m.) 4 m 6 f m Proposition 8. (ii) 3f = e + m 4m + 6(f m) = e. (b) m (Determine m. Show work!) Proposition 8. (i) 3 v = e (a) 3f = e + m Theorem 8.1 3 6 = 3v 3e + 3f = e 3e + e + m = m m = 6
Page 6 of 6 10. B 77 1 13 77 (Mr. B played games 77 consecutive days. Suppose he played at least one game each day but the total number of games is at most 13. Show that there is a certain consecutive period he played exactly 77 games. By a certain consecutive period, we mean for example, from the 3rd day to the 57th day.) b 1 b... b 77 77 1 b 1 < b < < b 77 13. Case 1. b 1, b,..., b 77 77 b i 1 b i 13 77 b i = 77 i 77 Case. b 1, b,..., b 77 77 b 1 b 77 77 p 1 p 77 r 1 r 77 b 1 = 77p 1 + r 1,..., b 77 = 77p 77 + r 77 77 77 0 1 r 1 76,... 1 r 77 76 77 1 76 b i, b j b i > b j b i = 77p i + r i, b j = 77p j + r j r i = r j b i b j = 77(p i p j ) b i b j 77 13 b i b j = 77 i j j + 1 i 77 77