Honors Introduction to Discrete Structures
COT 3100H Exam #2: Counting, Probability, Induction, Number Theory
Date: 3/20/08
Solution
1) (15 pts) Each of the following questions will deal with permutations of the letters in "HILLARYCLINTON"
a) How many permutations are there utilizing all of the letters in HILLARYCLINTON?
The number of permutations is , since there are 14 total letters, of which there are 2 I's, 3 L's, and 2 N's. (1 pt for numerator, 1 for fraction, 3 pts for denominator)
b) How many combinations of distinct consonants are there from the letters in HILLARYCLINTON? (Y is a consonant.)
The number of different consonants is 7 (H, L, R, Y, C, N, T). Thus the number of combinations of these consonants is just 27. (2 for consonant count, 3 for answer)
c) How many permutations of the letters in HILLARYCLINTON have two vowels adjacent to one another? (A, E, I, O, and U are vowels.)
We will count the number of permutations with no two adjacent vowels instead. There are a total of 4 vowels and 10 consonants. Imagine setting up the letters as follows:
_ H _ L _ L _ R _ Y _ C _ L _ N _ T _ N _
The locations of the vowels would be chosen amongst the 11 "blanks" indicated. This can be done in ways. The four vowels, once the locations are determined, can be ordered in ways. Finally, the consonants can be ordered in ways. Multiply each of these components to get arrangements with no two adjacent vowels. To get the final answer, subtract this from the total number of permutations to yield . (2 pts for 11 choose 4, 2 pts for factorials, 1 pt for subtract)
2) (5 pts) Given n sets of parentheses (n open parentheses and n close parentheses), the probability that a random permutation of them forms a valid arrangement of parentheses is 0.01. What is the value of n?
The number of valid sets of parentheses is . The total number of possible arrangements is .Thus, the desired probability is simply . It follows that n = 99. (3 pts for stating Catalan number, 1 pt for total number of arrangements, 1 pt for answer)
3) (15 pts) A store has 20 parking spaces in a row. After 15 people have parked randomly, what is the probability that two (or more) of the five open spaces are adjacent?
This is similar to part (c) of question #1. We will count the number of arrangements without adjacent parking spots and subtract from the total number of arrangements, which is . Place the fifteen parked cars in spots as follows:
_ P _ P _ P _ P _ P _ P _ P _ P _ P _ P _ P _ P _ P _ P _ P _
Thus we can choose the empty spots in ways, since there are 16 "blanks" of which 5 are for the empty car spots. Thus, the number of parking arrangements with two adjacent spots is simply . It follows that the desired probability is
4 pts for 20 choose 15, 6 pts for 16 choose 5, 3 pts for subtraction, 2 pts for division
4) (10 pts) The probability that Dwight Howard posts a double-double in a single game is 90%. If he does post a double-double, the Magic win 75% of the time. If he does NOT post a double-double, the Magic win 50% of the time. Given that the Magic lost a game, what is the probability that Dwight Howard posted a double-double?
.25 L
------* .225
|
.9 DD | .75 W
Here's the probability tree: *------*------* .675
| .5 W
------*------* .05
.1 No DD |------* .05
.5 L
(5 pts for tree, 2 pts for formula,
3 pts for plugging in correct vals)
5) (10 pts) Let S be the set of all of the divisors of 64. Let T contain the reciprocals of all the values in S. Explain why the sum of the values in T is .
The sum of the values in S is , as discussed in class. The sum of the reciprocals of these values is . We can find this sum as follows:
.
At this point, if you carefully look at the last double sum, you'll notice that the values being summed are EXACTLY the same as the values in S. The only difference is the order of summation (2434 is summed first instead of 2030.) Thus, we find that the sum of the values in T is , as desired. (The formula for the sum of the divisors of an integer was given in class also.)
2 pts for writing sum of reciprocals. 2 pts for factoring out 64. 2 pts for recognizing the same sum in the numerator, 2 pts for the sum of divisors formula, 2 pts for simplifying
6) (15 pts) Find all integer solutions to the equation 602x + 217y = 7.
602 = 2x217 + 168
217 = 1x168 + 49
168 = 3x49 + 21
49 = 2x21 + 7
21 = 3x7
49 – 2x21 = 7
49 – 2x(168 – 3x49) = 7
49 – 2x168 + 6x49 = 7
7x49 – 2x168 = 7
7x(217 – 168) – 2x168 = 7
7x217 – 9x168 = 7
7x217 – 9x(602 – 2x217) = 7
7x217 – 9x602 + 18x217 = 7
25x217 – 9x602 = 7
Thus, one solution is x = -9 and y = 25. (10 points, 1 pt per step)
To find all other solutions, consider the equation
602x = 217y and divide through by 7 (gcd(602, 217)) to get
86x = 31y. The smallest positive integer solution to this equation is x =31, y = 86.
(3 pts)
It follows that all solutions of the original equation are of the form
x = -9 + 31n, y = 25 – 86n, where n is an integer. (2 pts more)
7) (10 pts) Use induction to show that for all positive integers n.
Base case: n=1 LHS = , RHS = ,
so the base case is true. (1 pts)
Inductive hypothesis: Assume for an arbitrary integer n=k that . (1 pt)
Inductive step: Prove for n=k+1 that (1 pts)
(2 pts)
, using the inductive hypothesis (2 pts)
, multiplying out the matrices (1 pt)
, using exponent rules for simplication. (2 pt)
Thus, it follows that the assertion is true for all positive integers n.
8) (15 pts) Prove that 49 | (23n – 7n – 1) for all non-negative integers n.
Base case: n=0: 23(0) – 7(0) – 1 = 1 – 0 – 1 = 0, which is divisible by 49
so the statement is true for n=0. (1 pt)
Inductive hypothesis: Assume for an arbitrary integer n=k that 49 | (23k – 7k – 1). (2 pts)
Inductive step: Prove for n=k+1 that 49 | (23(k+1) – 7(k+1) – 1). (2 pts)
23(k+1) – 7(k+1) – 1 = 23k+3 – 7k – 7 – 1 (1 pt)
= 2323k – 7k – 8 (1 pt)
= 8(23k) – 7k – 49k + 49k – 8 (2 pts)
= 8(23k) – 56k – 8 + 49k (1 pt)
= 8(23k) – 8(7k) – 8 + 49k (2 pts)
= 8(23k – 7k – 1) + 49k (1 pt)
= 8(49c) + 49k, for some integer c, utilizing the IH. (1 pt)
= 49(8c + k), proving the assertion. (1 pt)
It follows that the given statement is true for all non-negative integers n.
9) (5 pts) On what day of the week did Palm Sunday occur? SUNDAY