\documentclass[11pt]{exam} \usepackage{graphicx} \usepackage{anysize} \usepackage{dsfont} \usepackage{fullpage} \usepackage{verbatim} \usepackage{url,amsfonts, amsmath, amssymb, amsthm,color, enumerate, multicol} \usepackage{placeins} \printanswers %\noprintanswers \begin{document} \title{ EECS 203: Discrete Mathematics \\ Individual Homework 7 (Winter 2016)} \date{Due: June 16, 2016} \author{Answer Key} \maketitle \begin{questions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 6.5 Problem 32\\ %% \begin{solution} We can treat the 3 consecutive A's as one letter. Thus we have 6 letters, of which 2 are the same (the two R's), so by Theorem 3 the answer is 6!/2! = 360. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 6.5 Problem 40\\ %% \begin{solution} We can describe any such travel in a unique way by a sequence of 4 x's, 3 y's, 5 z's, and 4 w's. By Theorem 3, there are $$\frac{16!}{4!3!5!4!}$$ such sequences. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[1] Section 7.1 Problem 8\\ %% \begin{solution} We saw in Example 11 of Section 6.3 that there are C(52, 5) possible poker hands, and we assume by symmetry that they are all equally likely. In order to solve this problem, we need to compute the number of poker hands that contain the ace of hearts. There is no choice about choosing the ace of hearts. To form the rest of the hand, we need to choose 4 cards from the 51 remaining cards, so there are C(51, 4) hands containing the ace of hearts. Therefore the answer to the question is the ratio $$\frac{C(51, 4)}{C(52,5)}=\frac5{52}\approx9.6\%$$ The problem can also be done by subtracting from 1 the answer to Exercise 9, since a hand contains the ace of hearts if and only if it is not the case that it does not contain the ace of hearts. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[1] Section 7.1 Problem 38 (a,c)\\ %% \begin{solution} \begin{enumerate}[a)] \item Intuitively, these should be independent, since the first event seems to have no influence on the second. In fact we can compute as follows. First $p(E_1) = 1/2$ and $p(E_2) = 1/2$ by the symmetry of coin tossing. Furthermore, $E_1\cap E_2$ is the event that the first two coins come up tails and heads, respectively. Since there are four equally likely outcomes for the first two coins (HH , HT , TH , and TT ), $p(E_1 \cap E_2) = 1/4$. Therefore $p(E_1 \cap E_2) = 1/4 = (1/2) \cdot (1/2) = p(E_1)p(E_2)$, so the events are indeed independent. \addtocounter{enumi}{1} \item Again $p(E_1) = 1/2$. For $E_2$ , note that there are 8 equally likely outcomes for the three coins, and in 2 of these cases $E_2$ occurs (namely HHT and THH ); therefore $p(E_2) = 2/8 = 1/4$. This time $p(E_1 \cap E_2) = 0$, since there is no way to get two heads in a row if the second coin comes up tails. Since $p(E_1)p(E_2) \neq p(E_1 \cap E_2)$, the events are not independent. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Redo the Monty Hall problem, but this time with 10 doors (1 winner, the rest a goat) where the host opens 5 non-winning doors. What is the probability of winning if you switch after he reveals those doors? What is the probability of winning if you don’t switch? \\ %% \begin{solution} Initially, if you pick a door, there is a 1/10 chance that you pick the winning door. This means there is a 9/10 chance that the winning door is among the others. When the 5 non-winning doors are opened, there is still a 9/10 chance that your initial pick is wrong, in which case, you have a 1 in 4 chance of changing to the correct door. This means if you change doors, you have a 9/40 chance winning. This is better than the 1/10=4/40 chance you would have if you stayed. \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[3] Section 7.2 Problem 18\\ %% \begin{solution} As instructed, we assume that births are independent and the probability of a birth in each day is 1/7. (This is not exactly true; for example, doctors tend to schedule C-sections on weekdays.) \begin{enumerate}[a)] \item The probability that the second person has the same birth day-of-the-week as the first person (whatever that was) is 1/7. \item We proceed as in Example 13. The probability that all the birth days-of-the-week are different is $$p_n=\frac67\cdot \frac57\cdot...\cdot\frac{8-n}7$$ since each person after the first must have a different birth day-of-the-week from all the previous people in the group. Note that if $n \geq 8$, then $p_n = 0$ since the seventh fraction is 0 (this also follows from the pigeonhole principle). The probability that at least two are born on the same day of the week is therefore $1 - p_n$ . \item We compute $1 - p_n$ for $n = 2, 3, . . .$ and find that the first time this exceeds 1/2 is when n = 4, so that is our answer. With four people, the probability that at least two will share a birth day-of-the-week is 223/343, or about 65\%. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 7.3 Problem 10\\ %% \begin{solution} Let A be the event that a randomly chosen person in the clinic is infected with avian influenza. We are told that p(A) = 0.04 and therefore $p(\overline{A}) = 0.96$. Let P be the event that a randomly chosen person tests positive for avian influenza on the blood test. We are told that $p(P | A) = 0.97$ and $p(P | \overline{A}) = 0.02$ (“false positive”). From these we can conclude that $p(\overline{P} | A) = 0.03$ (“false negative”) and $p(\overline{P} | \overline{A}) = 0.98$. \begin{enumerate}[a)] \item We are asked for $p(A | P)$. We use Bayes’ theorem: $$p(A|P)=\frac{p(P|A)p(A)}{p(P|A)p(A)+p(P|\overline{A})p(\overline{A})}=\frac{(0.97)(0.04)}{(0.97)(0.04)+(0.02)(0.96)}\approx 0.669$$ \item In part (a) we found $p(A | P)$. Here we are asked for the probability of the complementary event (given a positive test result). Therefore we have simply $p(A | P) = 1 - p(A | P) \approx 1 - 0.669 = 0.331$. \item We are asked for $p(A | \overline{P})$. We use Bayes’ theorem: $$p(A|\overline P)=\frac{p(\overline P|A)p(A)}{p(\overline P|A)p(A)+p(\overline P|\overline{A})p(\overline{A})}=\frac{(0.03)(0.04)}{(0.03)(0.04)+(0.98)(0.96)}\approx0.001$$ \item In part (c) we found $p(A | \overline P)$. Here we are asked for the probability of the complementary event (given a negative test result). Therefore we have simply $p(\overline A | \overline P) = 1 - p(A | \overline P) \approx 1 - 0.001 = 0.999$. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[3] Section 7.3 Problem 16\\ %% \begin{solution} Let L be the event that Ramesh is late, and let B, C , and O (standing for “omnibus”) be the events that he went by bicycle, car, and bus, respectively. We are told that $p(L | B) = 0.05$, $p(L | C) = 0.50$, and $p(L | O) = 0.20$. We are asked to find $p(C | L)$. \begin{enumerate}[a)] \item We are to assume here that $p(B) = p(C) = p(O) = 1/3$. Then by the generalized version of Bayes’ theorem, $$p(C|L)=\frac{p(L|C)p(C)}{p(L|B)p(B)+p(L|C)p(C)+p(L|O)p(O)}$$ $$=\frac{(0.5)(1/3)}{(0.05)(1/3)+(0.5)(1/3)+(0.2)(1/3)}=\frac23$$ \item Now we are to assume here that p(B) = 0.60, p(C) = 0.30, p(O) = 0.10. Then by the generalized version of Bayes’ theorem, $$p(C|L)=\frac{p(L|C)p(C)}{p(L|B)p(B)+p(L|C)p(C)+p(L|O)p(O)}$$ $$=\frac{(0.5)(0.3)}{(0.05)(0.6)+(0.5)(0.3)+(0.2)(0.1)}=\frac34$$ \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 8.1 Problem 8\\ %% \begin{solution} This is very similar to Exercise 7, except that we need to go one level deeper. \begin{enumerate}[a)] \item Let $a_n$ be the number of bit strings of length n containing three consecutive 0’s. In order to construct a bit string of length n containing three consecutive 0’s we could start with 1 and follow with a string of length n-1 containing three consecutive 0’s, or we could start with a 01 and follow with a string of length n-2 containing three consecutive 0’s, or we could start with a 001 and follow with a string of length n - 3 containing three consecutive 0’s, or we could start with a 000 and follow with any string of length n - 3. These four cases are mutually exclusive and exhaust the possibilities for how the string might start. From this analysis we can immediately write down the recurrence relation, valid for all $n \geq 3: a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3}$ . \item There are no bit strings of length 0, 1, or 2 containing three consecutive 0’s, so the initial conditions are $a_0 = a_1 = a_2 = 0$. \item We will compute $a_3$ through $a_7$ using the recurrence relation: $$a_3 = a_2 + a_1 + a_0 + 2^0 = 0 + 0 + 0 + 1 = 1$$ $$a_4 = a_3 + a_2 + a_1 + 2^1 = 1 + 0 + 0 + 2 = 3$$ $$a_5 = a_4 + a_3 + a_2 + 2^2 = 3 + 1 + 0 + 4 = 8$$ $$a_6 = a_5 + a_4 + a_3 + 2^3 = 8 + 3 + 1 + 8 = 20$$ $$a_7 = a_6 + a_5 + a_4 + 2^4 = 20 + 8 + 3 + 16 = 47$$ Thus there are 47 bit strings of length 7 containing three consecutive 0’s. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 8.1 Problem 20\\ %% \begin{solution} We let $a_n$ be the number of ways to pay a toll of 5n cents. (Obviously there is no way to pay a toll that is not a multiple of 5 cents.) \begin{enumerate}[a)] \item The first coin paid can either be a nickel or a dime. If we start with a nickel, we have 5n-5=5(n-1) cents remaining to pay, which can be done in $a_{n-1}$ ways. Alternately, we could start with a dime. In this case, we have 5n-10=5(n-2) cents left, giving $a_{n-2}$ ways to finish it off. In total, this gives $a_n = a_{n-1} +a_{n-2}$ , with $a_0 = a_1 = 1$. \item Iterating, we find that $a_9 = 55$. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[1] Section 8.2 Problem 2acef \\ %% \begin{solution} \begin{enumerate} \item[a)] Yes. \item[c)] No, not linear. \item[e)] No, not constant coefficients. \item[f)] No, not homogeneous. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 8.2 Problem 4ag \\ %% \begin{solution} \begin{enumerate} \item[a)] The characteristic equation is $r^2 - r - 6 = 0$, and so the roots are $-2$ and $3$. Our closed form is $a_n = \alpha_1 (-2)^n + \alpha_2 3^n$. Using the initial conditions, we get that $3 = \alpha_1 + \alpha_2$ and $6 = -2\alpha_1 +3\alpha_2$, so $\alpha_2 = 12/5$ and $\alpha_1 = 3/5$. Therefore, our closed form is $a_n = 3/5 \cdot (-2)^n+12/5\cdot 3^n$. \item[g)] The characteristic equation is $r^2 + 4r - 5 = 0$, so the roots are $-5$ and $1$. Our closed form is $a_n = \alpha_1 (-5)^n + \alpha_2 1^n$. Using the initial conditions, we get that $2 = \alpha_1 + \alpha_2$ and $8 = -5 \alpha_1 + \alpha_2$. From this, we see get that $\alpha_1 = -1$ and $\alpha_2 = 3$. Therefore, our closed form is $a_n = - (-5)^n + 3$. \end{enumerate} \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 8.2 Problem 6 \\ %% \begin{solution} One thing is unclear: If we can send no signal or not. We'll assume we cannot (or no signal is already one of the signals). With n ms, we can send any message we could send with n-1 ms plus the 1 ms signal. Or we could send any message we could send with n-2 ms plus either of the 2ms signals. That gives us a recurence relation of $a_n=a_{n-1}+2a_{n-2}$ with initial conditions of $a_0=1$ and $a_1=1$. The characteristic equation is $r^2-r-2$ which has roots of 2 and -1. Thus the solution is of the form $\alpha_1(2)^n+\alpha_2(-1)^n$ For n=0 we get $a_0=1=\alpha_1+\alpha_2$. For n=1 we get $a_1=1=2\alpha_1-\alpha_2$ We get $\alpha_1={\frac23}$ and $\alpha_2={\frac13}$ And thus the closed form solution is ${\frac23}2^n+{\frac13}(-1)^n$ \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[3] Find a solution to the following recurrence relation: $$a_n=3a_{n-2}+2a_{n-3}$$ $$a_0=2, a_1=2, a_2=1$$ \\ %% \begin{solution} The characteristic equation is $r^3-3r-2$. The roots are -1, -1 and 2. So we've got repeated roots. We then expect our solution to be of the form $\alpha_1(-1)^n+\alpha_2n(-1)^n+\alpha_3(2)^n.$. For n=0 we get $a_0=2=\alpha_1+0\alpha_2+\alpha_3 = \alpha_1+\alpha_3$. For n=1 we get $a_1=2=-\alpha_1-\alpha_2+2\alpha_3$. For n=2 we get $a_2=1=\alpha_1+2\alpha_2+4\alpha_3$ Solving, we get $$a_n={\frac79} 2^n+{\frac{11}9} (-1)^n - {\frac53} n(-1)^n$$ \end{solution} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \question[2] Section 8.3 Problem 18\\ %% \begin{solution} There is a bit of a problem with this question. In particular the main body of the question claims that you need "more than n/2 votes" but the part a description just requires n/2 notes. We will assume the main body is the correct version. If you assume otherwise, the final answer would have an additional 8n comparisons at most which still gives the same complexity. The key observation is that there are 2n votes total (n people each with 2 votes). If you split the voters in half, the only way a person can get more than n/2 votes is if they are in at least 3rd place in one of the two halves. That's because the 4th place finisher on each side can have at most one 4th of the votes (if tied with the other 3) and so they can only get n/4 votes of the n possible votes in that half. If they are 4th in both halves, they can at most get n/2 votes, which is less than the "more than n/2 votes". So, our recursive algorithm will take a sequence of names and determine whether one name occurs as more than 1/4th of the elements of the sequence, and if so, what those names are. If the sequence has just two elements (the two votes from one person),then the two people on the list have more than 1/4th of the vote. For the recursive step, divide the list into two parts-the first half and the second half-as equally as possible. Apply the algorithm recursively to each half to come up with at most six names. Then run through the entire list to count the number of occurrences of each of those names to decide which, if any, have more than 1/4th of the votes. This requires at most 6n additional comparisons for a list of length n. b) We apply the master theorem with a = 2 , b = 2 , c = 6 , and d = 1 . Since $a = b^d$ , we know that the number of comparisons is $O(n^d \log n) = O(n\log n)$. \end{solution} \end{questions} \end{document}