COT 3100H Spring 2003 Introduction to Discrete Structures Final Exam April 24 2003 Name 1 10 pts Find a closed form solution for the following recurrence relation without using generating functions t 0 7 t 1 18 t n 5t n 1 6t n 2 for all integers n 1 2 10 pts Use the method of generating functions to solve the following recurrence relation s 0 3 s 1 3 s n 5s n 1 14s n 2 for all integers n 1 3 10 pts Let S be a set of five positive integers the maximum of which is at most 10 Prove that there exist two non empty disjoint subsets of S that have the same sum of elements Note Two subsets can be disjoint even if the values of the elements in the two sets are equal For example two disjoint subsets of 1 2 3 3 4 are 1 3 and 3 4 since there are two copies of three in the set We can think of the original set being a b c d e where a 1 b 2 c 3 d 3 e 4 and the two subsets as being a c and d e 4 8 pts Let x be a positive integer greater than 1 Prove using induction on n that x n 1 is divisible x 1 for all positive integers n 5 12 pts Choose one of the two following questions n 1 2 n 1 1 for all positive integers n i Note You may use either induction or another proof technique shown in class Although the induction works a portion of it is tricky a Prove i 1 b Prove 21 4n 1 52n 1 for all positive integers n using induction 6 8 pts Use the laws of logic to show that the two following expressions are logically equivalent a p q b p r p r q q r 7 4 pts a Find gcd 705 450 using Euclid s Algorithm 6 pts b Find integers x and y such that 705x 450y gcd 705 450 8 10 pts For any arbitrary sets A B and C from the same universe prove that if and only if A B C A B C then A C 9 16 pts A committee of 10 senators is to be chosen from the 100 U S senators 45 of these senators are senior members while 60 of them are men Of the women senators 30 of them are not senior members Given the following restrictions how many possible committees can be picked Note All four parts are independent of each other a The committee is required to have at least two senior members b The committee must have exactly five members that are either men or senior members c The committee is entirely comprised of men that are not senior members and women that are senior members d The committee contains no men and contains no non senior members 10 10 pts A gardener plants three maple trees four oak trees and five birch trees in a row He plants them in random order each arrangement being equally likely Find the probability that no two birch trees are next to one another 11 12 pts In each of the following examples R S and T are all relations over the set of integers Z Find a counter example to disprove each of the following claims a If R R is symmetric then R is symmetric b If R R R is transitive then R is transitive c If R S T S then R T d R x y x 2y y 2x x y R is an equivalence relation 12 18 pts Let f g and h be functions over finite sets A B C and D with f A B g B C h C D such that h g f x is a bijection a Prove that h must be a surjection and f must be an injection b Show that it is possible for h to not be injective f to not be surjective and g to be neither Show this using one single example Please specify the sets A B C D and the functions f g and h in your example n 13 10 pts Find k 1 1 k 1 k Hint rationalize the denominator before determining the sum 14 2 pts In what country did the Spanish Civil War take place 15 2 pts In what city is the Washington monument 16 2 pts What company produces the Honda Accord
View Full Document
Unlocking...