discrete-niii
strength
test3.pdf
Math 208 Correspondence Lesson 21N: Exam 3 Name: TIME LIMIT: 2 hours; 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 12x ≡ 4(mod 8) is solvable.
3. True False:
( 25
15
) >
( 25
10
) .
4. True False: When (2x + 1)30 is expanded, the coefficient of x10 is
( 30
10
) .
5. True False: If A and B are finite sets, then |A∪B| is always less than or equal to |A| + |B|.
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: an = n 2 is a solution to the recurrence a0 = 0 and for n ≥ 1,
an = an−1 + 2n− 1.
10. True False: There is a graph with degree sequence 0, 1, 2, 3.
11. True False: The number of strings of five 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 {a, b, c · · · , z, 0, 1, 2 · · ·9} consisting
two elements is
( 26
2
) +
( 10
2
) .
Part II: (5 points each) Multiple Choice (circle your answer):
1) Recall that Kn is the simple graph with n vertices with every pair of vertices adjacent (the complete graph on n vertices). Circle all n for which Kn has a Eulerian cycle.
(a) 3
(b) 4
(c) 5
(d) 6
(e) 7
2) When 3625 is divided by 17, the remainder is
(a) 0
(b) 1
(c) 2
(d) 3
(e) None of the above.
3) The number of different 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 a or end with z is
(a) 2(268)
(b) 268
(c) 269 + 269
(d) (269)(269)
(e) None of the above.
Page 2
5) In a listing of the five 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 Σ = {a, b, c, d} that contain at least one d is
(a) 104 − 93
(b) 104 − 94
(c) 104 − 103
(d) 410 − 39
(e) 410 − 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 different ways he can climb a flight of n steps is:
(a) an = an−1 + an−2
(b) an = an−1 + an−3
(c) an = an−2 + an−3
(d) an = (an−1 − 1) + (an−2 − 2) (e) an = (an−1 − 1) + (an−3 − 3)
8) When looking for a particular solution to the recurrence an = 2an−1 + an−2 + 2 n + 1 your
first try should be
(a) an = 2 n + B
(b) an = A(2 n) + 1
(c) an = A(2 n) + B
(d) an = A(2 n) + B(−2)n + 1
(e) an = 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 defined recursively by a0 = 0, a1 = 1, and for n ≥ 2, an = 2an−1 + 15an−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
cd
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
