Page 1 of 6 B (The World of Mathematics) November 20, 2006 Final Exam 2006 Division: ID#: Name: 1. p, q, r (Let p, q, r are propositions. ) (10pts) (a

Size: px

Start display at page:

Download "Page 1 of 6 B (The World of Mathematics) November 20, 2006 Final Exam 2006 Division: ID#: Name: 1. p, q, r (Let p, q, r are propositions. ) (10pts) (a"

しょうこふじした
4 years ago
Views:

1 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

2 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 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.) (Total)

3 Page 3 of (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.)

4 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) (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.)

5 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.) 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!)

6 Page 6 of B (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.

7 Page 1 of 6 B (The World of Mathematics) November 0, 006 Solutions to Final Exam 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))

8 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 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.) = C (Find the minimum cost of a connected network using the diagram below. Draw your network on the right as well by connecting corresponding points.) (Total) 1 ( )

9 Page 3 of (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.) v = 6 e = 9 v e + f = f = e v + = = 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 = 0.

10 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.) A 19 A A A A A (b) (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 A A 17 A 7. (Show that the graph below is not a Hamilton graph.) Theorem Bipartite

11 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 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 = 3v 3e + 3f = e 3e + e + m = m m = 6

12 Page 6 of B (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 b 1 < b < < b Case 1. b 1, b,..., b b i 1 b i b i = 77 i 77 Case. b 1, b,..., b b 1 b p 1 p 77 r 1 r 77 b 1 = 77p 1 + r 1,..., b 77 = 77p 77 + r r 1 76,... 1 r 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 b i b j = 77 i j j + 1 i 77 77

Quiz 1 ID#: Name: 1. p, q, r (Let p, q and r be propositions. Determine whether the following equation holds or not by completing the truth table belo

Quiz 1 ID#: Name: 1. p, q, r (Let p, q and r be propositions. Determine whether the following equation holds or not by completing the truth table below.) (p q) r p ( q r). p q r (p q) r p ( q r) x T T