Problem #1 (Short answer grab-bag) [10 pts] |
|
For parts (a)-(c), justify your answer briefly. a. [2 pts] True or false: (P -> Q) -> (Q -> P) always holds, for all propositions P, Q. False. A counterexample: P = False, Q = True. This is a converse error. b. [3 pts] True or false: ((P OR Q) -> Q) -> (Q -> (P OR Q)) always holds, for all propositions P, Q. True. (Q -> (P OR Q)) = True for all P, Q, and (anything -> True) is true. (Don't be fooled into thinking this is another converse error. It's not.) (A common error: Not realizing that (False -> False) is True.) c. [3 pts] Recall that two sets S, T are said to be disjoint if S AND T = NULL. Can two events A and B be simultaneously independent and disjoint? Yes. An example: If A = NULL, then A AND B = NULL and Pr[A] = 0, so Pr[A AND B] = 0 = 0 * Pr[B] = Pr[A]Pr[B], and A, B are independent and disjoint. d. [2 pts] Recall that two random variables X and Y are independent just if the pair of events X = i and Y = j are independent no matter how you choose the values i and j. Which of the following most accurately expresses the proposition that X and Y are not independent? (You do not need to justify your answer.) (i) for all i,j. Pr[X = i AND Y = j] not = Pr[X = i]Pr[Y = j] (ii) for all i, some j. Pr[X = i AND Y = j] not = Pr[X = i]Pr[Y = j] (iii) for some j, all i. Pr[X = i AND Y = j] not = Pr[X = i]Pr[Y = j] (iv) for some i, j. Pr[X = i AND Y = j] not = Pr[X = i]Pr[Y = j] IV |
Problem #2 (Permutations) [25 pts] |
|
Let S be the sample space of all permutations on the n letters {1, 2, ..., n}, with the uniform probability distribution. in each of the following, give reasons for all your answers. (You may find the next page, which has been left blank, useful for justifying your answers.) a. [1 pt] The uniform probability distribution assigns to every permutation on n letters the probability: 1/n!, since each of the n! permutations is assigned the same probability, and these probabilities must sum to 1. Define the random variable Xi to be the number of cycles of length i, i.e., Xi maps each permutation to an integer equal to the number of cycles in that permutation that are of length i. b. [1 pt] For the permutation (124)(36)(5)(7) on n = 7 letters: X1 = 2, X2 = 1, X3 = 1, X4 = 0 For general positive integers n, give: c. [3 pts] E[X1] = 1 d. [7 pts] E[X2] = 1/2 For an integer k in set {1, 2, ..., n}, what is e. [8 pts] E[Xk] = 1/k. Define the random variable X to be the number of cycles in a permutation. In other words, X maps any permutation to a positive integer equal to the number of cycles in that permutation. f. [1 pt] For the permutation (124)(36)(5)(7), X = 4 g. [1 pt] Is X = X1 + X2 + ... + Xn? Yes h. [3 pts] E[X] = Hn = sum(k = 1 to n)1/k Give reasons for all your answers below. c. Define random variable Xi = {1 if i -> i, 0 otherwise Note that X1 = sum(i = 1 to n)Xi, so by linearity of expectation, E[X1] = sum(i = 1 to n)E[Xi] = sum(i = 1 to n)Pr[i->i] = sum(i = 1 to n)1/n = 1 d. Define random variable Xi = {1/2 if i and j form a cycle for some j not = i, 0 otherwise Note that X2 = sum(i = 1 to n)Xi, so by linearity of expectation, E[X2] = sum(i = 1 to n)E[Xi] Now E[Xi] = Pr[Xi = 1/n] * 1/2 = (n-1)/n * 1/(n-1) * 1/2 = 1/(2n), so E[X2] = sum(i = 1 to n)1/(2n) = 1/2 e. Define random variable Xki = {1/k if i participates in cycle of length k, 0 otherwise E[Xki] = 1/k * Pr[Xki = 1/k] = 1/k * ((n-1)/n * (n-2)/(n-1) * ... 1/(n*k+1)) = 1/(kn) Also E[Xk] = sum(i = 1 to n)E[Xki] = sum(i = 1 to n)1/(kn) = 1/k g. X = # of cycles = (# cycles of length 1) + (# cycles of length 2) + ... = X1 + X2 + ... + Xn h. E[X] = E[X1] + E[X2] + ... + E[Xn] = 1 + 1/2 + ... + 1/n = Hn |
Problem #3 (Tiling) [15 pts] |
|
Let Dn be the number of ways to tile a 2 x n checkerboard with dominos, where a domino is a 1 x 2 piece. Prove that Dn <= 2^n for all positive integers n. (HINT: find a recurrence relation) Note that every 2 x n tiling takes one of the following two forms: a. One vertical domino on the left b. Two horizontal, stacked dominos on left These two cases are mutually exclusive and exhaust the possibilities, and there are D(n-1) configurations of form (a) and D(n-2) of (b). Therefore Dn = D(n-1) + D(n-2) for n >= 2 D0 = D1 = 1 Claim: Dn <= 2^n for all n >= 0 Proof: By strong induction on n. Base case: D0 = 1 <= 2^0 and D1 = 1 <= 2^1, so the claim is true for n = 0 and n = 1 Inductive step: We show for all k >= 2 (D0 <= 2^0 AND ... AND D(k-1) <= 2^(k-1)) -> Dk <= 2^k. Assume D0 <= 2^0 AND ... AND D(k-1) <= 2^(k-1). Then Dk = D(k-1) + D(k-2) <= 2^(k-1) + 2^(k-2) = (1/2 + 1/4) * 2^k <= 2^k as claimed This completes the proof Common errors (#3) Not justifying the recurrence relation. You were asked to write a proof; if your proof depends on a recurrence relation, you need to argue why the recurrence relation is correct. "Backwards induction." In the inductive step, where you must prove a statement of the form P->Q, many people assumed Q and manipulated it to get something that looks like P, and called that a proof. Example: Claim: 2x - 5 >= 0 for all x "Proof": 2x - 5 >= 0 (line 1) 2x >= 5 (line 2) 0 * (2x) >= 0 * 5 (line 3) 0 >= 0 (line 4) Do you see what's wrong with this proof? First, it is backwards: It starts with the conclusion to be proved, whereas a correct proof should start with the hypothesis and derive the conclusion from it. If you think this is "just" a matter of writing statements in the reverse order, look again: line 2 does not follow from line 3. In fact, the claim is not even true. So: avoid this error. A tip: try writing out the proof in English(e.g., "x >= 0, so therefore x + 1 >= 1,..."), and see if everything makes sense. An alternative proof (#3): A 2 x n board has 2n squares, and each domino takes up 2 of those, so all tilings must use exactly n dominos. Imagine placing these n dominos on the board, one at a time, from leftmost to rightmost. (In case of ambiguity - e.g., two horizontal dominos stacked on top of each other resolve by placing topmost dominos before bottom-most ones.) As you place each domino, there will be at most 2 ways to place it: in a vertical orientation, or in a horizontal location. The left-to-right (top-to-bottom) ordering ensures you will have no choice about the location of each domino. You might not have 2 choices of orientation, but you'll always have at most 2 choices. Since there are only n dominos, there are at most 2^n ways to tile the board. (Note that the observations about ordering are crucial to the correctness of this proof, and should not be omitted.) |