Discrete Mathematics Practice Exam
Math 208 Correspondence Lesson 21N: Exam 3 Name:
TIME LIMIT:
2hours; no books, no notes, no calculators, etc Part I: (2 1 2 points each)True or False (circle your answer):
1. True False : 122 44( mod 3).
2. True False : The congruence equation 12 x 4( mod 8) is solvable.
3. True False : 25 15 > 25 10 .
4. True False : When (2x+ 1) 30 is expanded, the coe cient of x10 is 30 10 .
5. True False : IfAand Bare nite sets, then jA [Bjis always less than or equal to jA j+ jB j:
6. True False : 7059 days after a Monday is a Friday.
7. True False : In a group of 200 people, we can be sure there are at least 30 born on the same day of the week.
8. True False : There is no closed form formula for the Fibonacci sequence.
9. True False :a n = n2 is a solution to the recurrence a 0 = 0 and for n 1, a n = a n 1 + 2 n 1.
10. True False : There is a graph with degree sequence 0 ;1 ;2 ;3.
11. True False : The number of strings of ve letters from the usual alphabet if repeats are not allowed is 26! 21!
.
12. True False : The number of ways of picking a subset of fa; b; c ; z;0;1 ;2 9g consisting two elements is 26 2 + 10 2 . Part II: (5 points each)Multiple Choice (circle your answer):
1) Recall that K n is the simple graph with nvertices with every pair of vertices adjacent (the complete graph on nvertices). Circle all nfor which K n has a Eulerian cycle.
(a) 3 (b) 4 (c) 5 (d) 6 (e) 7 2) When 36 25 is divided by 17, the remainder is (a) 0 (b) 1 (c) 2 (d) 3 (e) None of the above.
3) The number of di erent poker hands (5 cards, order not important, selected from a 52 card deck) with 3 red cards and 2 black cards is:
(a) 26 3 26 2 (b) 52 5 26 23 26 24 (c) 26 3 + 26 2 (d) 52 5 26 23 26 24 (e) None of the above.
4) The number of strings of length 10 of the 26 letters that either begin with aor end with z is (a) 2(26 8 ) (b) 26 8 (c) 26 9 + 26 9 (d) (26 9 )(26 9 ) (e) None of the above.
Page 2 5) In a listing of the ve equivalence classes modulo 5, four of the values are 11, 8, 100, and 32. The last value could be (a) 0 (b) 1 (c) 2 (d) 3 (e) 4 6) The number of strings of length 10 from the alphabet = fa; b; c; d gthat contain at least one dis (a) 10 4 93 (b) 10 4 94 (c) 10 4 10 3 (d) 4 10 39 (e) 4 10 310 7) I. M. N. Oddman climbs stairs by taking either one or three steps at a time. A recursive formula for the number of di erent ways he can climb a ight of nsteps is:
(a) a n = a n 1 + a n 2 (b) a n = a n 1 + a n 3 (c) a n = a n 2 + a n 3 (d) a n = ( a n 1 1) + ( a n 2 2) (e) a n = ( a n 1 1) + ( a n 3 3) 8) When looking for a particular solution to the recurrence a n = 2 a n 1 + a n 2 + 2 n + 1 your rst try should be (a) a n = 2 n + B (b) a n = A(2 n ) + 1 (c) a n = A(2 n ) + B (d) a n = A(2 n ) + B( 2) n + 1 (e) a n = A(2 n ) + B( 2) n + C Page 3 Part III. (10 points each)Problems Do any three of the following four problems. If you do all four, I'll count your best three.
1) Determine the number of ways the 26 letters of the alphabet can be written in a row (no repeats) if the vowels ( a; e; i; o; u) must be adjacent.
2) You have inexhaustible supplies of red and blue marbles. The marbles are distributed randomly, one by one, into three tin cans. What is the minimum number of marble that have to be distributed to be absolutely sure there is a can with two marbles of the same color.
Page 4 3) Determine a closed form formula for the sequence de ned recursively by a 0 = 0, a 1 = 1, and for n 2, a n = 2 a n 1 + 15 a n 2.
4) Show the two graphs below are isomorphic by writing down a mapping (in other words, a pairing of the vertices) that is a graph isomorphism. Start with the pairing a! v. e a b c d G z v w xy H Page 5 BLANK PAGE TO BE USED FOR SCRATCH PAPER BLANK PAGE TO BE USED FOR SCRATCH PAPER BLANK PAGE TO BE USED FOR SCRATCH PAPER
