\documentstyle[12pt,macpsfig,amssymb]{article} \input{/a/class/6.042/fall94/handouts/macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} \newcommand{\pr}{\problem} \begin{document} \exam{Quiz 1}{October 19, 1991} \begin{closeitemize} \item This quiz ends at 9 {\sc p.m.} It contains ???? problems. You have 120 minutes to earn ????? points. \item This quiz is closed book. You may use one $8\frac{1}{2}''\times 11''$ handwritten crib sheet. \item Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Please do not put part of the answer to one problem on the back of the sheet for another problem. \item Do not spend too much time on any problem. Read them all through first and attack them in the order that allows you to make the most progress. \item Show your work, as partial credit will be given. You will be graded not only on the correctness of your answer, but also on the clarity with which you express it. Be neat. \end{closeitemize} \renewcommand{\arraystretch}{.5} \begin{center} \begin{tabular}{|c|c|c|} \hline & &\hspace*{1in}\\ Problem&Points&Grade\\ & &\\ \hline \hline & &\\ 1 & 10 & \\ & &\\ \hline & &\\ 2 & 10 & \\ & &\\ \hline & &\\ 3 & 10 & \\ & &\\ \hline & &\\ 4 & 10 & \\ & &\\ \hline & &\\ 5 & 10 & \\ & &\\ \hline & &\\ 6 & 10 & \\ & &\\ \hline & &\\ 7 & 10 & \\ & &\\ \hline & &\\ 8 & 10 & \\ & &\\ \hline & &\\ 9 & 10 & \\ & &\\ \hline & &\\ 10 & 10 & \\ & &\\ \hline \hline & &\\ Total & 100 & \\ & &\\ \hline \end{tabular} \end{center} \renewcommand{\arraystretch}{1} \bigskip \bigskip \bigskip \noindent Name:\ \mbox{}\hrulefill\mbox{}\par \newpage \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \pr \points{??} \bparts \ppart Let $p$ be a prime. Prove that if $p\bmod 3 = 1$ then $p\bmod 6 = 1$. \ppart Prove that $3\divides (n^3 + 2n)$ for all $n\in\nats$. \eparts \pr \points{??} \bparts \ppart Use the Euclidean algorithm to find the gcd of 221 and 323. \ppart Find an integer solution to $221x + 323y = 187$. \eparts % DONE BY RANDALL IN RECITATION. % \pr % \points{??} Use induction to prove that for any natural number $n>3$, % $n! > 2^n$. \pr \points{??} Let $G=(V,E)$ be a free tree, and define the relation\\ $R=\{(v_1,v_2)\in V\times V: \mbox{ there is a simple path of even length from $v_1$ to $v_2$} \}$. \bparts \ppart Prove that $R$ is an equivalence relation. \ppart What are the equivalence classes for the graph $G$ below? \eparts \pr \points{??} Let $R_1\subseteq S\times S$ and $R_2\subseteq S\times S$ be two equivalence relations on a set~$S$. \bparts \ppart Is their union, $R_1\cup R_2$, an equivalence relation? Prove your answer. \ppart Is their intersection, $R_1\cap R_2$, an equivalence relation? Prove your answer. \eparts % \pr % \points{??} % Prove that the quotient and the remainder promised by the division % algorithm when $a\in\nats$ is divided by $b\in\nats$ are unique. % % \pr % \points{??} % The media reported that the recent survey % {\em Sex in America$^{\sc pg-13}$} found that in America, men have % kissed(!) an average of six women and women have kissed an average of % two men. Comment from a graph-theoretic point of view. \pr \points{??} Circle {\bf T} or {\bf F} for each of the following statements to indicate whether the statement is true or false, respectively. Also justify your answer, concisely and succinctly. The justification counts for more points than simply the correct {\bf T}/{\bf F} answer. One- or two-sentence explanations or pictures should suffice. \begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}% \setlength{\labelwidth}{\leftmargin}% \addtolength{\labelwidth}{-\labelsep} } \item For all $a,b\in\ints$, every common divisor of $a$ and $b$ can be expressed in the form $ax + by$ for some $x,y\in\ints$. %\vspace*{1.25in} \item For any predicates $P(x)$ and $Q(x)$, we have $\forall x \left( P(x)\land \neg Q(x)\right) \implies \neg\exists x \left( P(x)\implies Q(x)\right)$. %\vspace*{1.25in} \item For any prime $p$, we have $p\divides 1\implies p^2+1 \mbox{ is odd}$. \item For any two different Fibonacci numbers $F_m$ and $F_n$, $\gcd(F_m,F_n)=1$. \item Every undirected graph in which each vertex has degree 3 has an even number of vertices. \item No relation can be both symmetric and antisymmetric. \item $f(x)=x^2-x$ is an injection from $\reals$ to $\reals$. \item $f(x)=x^2-x$ is a surjection from $\reals$ to $\reals$. \item If $C$ is a countable set then $C\times C$ is also countable. \item $n=o(2^{\sqrt{n}})$. \item $2^{\lg ^3n} = \Theta ( n^3)$. \item $\lg (n^3) = \Theta (\lg n)$. \item $n^{3.01} = \omega (n^3 \lg n)$. \item $3^{2n} \sim 9^n$. \item $e^{\ln (n^3)} = \Theta( n^3 )$. \item $1+{1\over 0.9} + \left(1\over 0.9\right)^2 + \left(1\over 0.9\right)^3 \cdots = {1\over 1-0.9} = 10$ \end{list} % \pr % \points{??} % Find an $f(n)$ in closed form such that % $f(n)\sim \sum_{i=1}^{n} i^{-1/2}$. \pr \points{??} % Easy form: % Show that in any set of 10 integers, there are four integers % $a_1,...,a_4$ such that for all $i,j$, $3\divides (a_i-a_j)$. % Hard form: Show that if $n>m(m-1)$, then in any set of $n$ integers there are $m$ integers $a_1,...,a_m$ such that for all $i,j$ we have $m\divides (a_i-a_j)$. \pr \points{??} Let $T_n$ denote the product of all positive even integers less than~$n$. \bparts \ppart Find a closed form expression for $T_n$. (You may leave factorials %and floor functions in your answer.) \ppart Find a function $f(n)$ that does not have sums, products, floors or factorials for which $f(n) \sim T_n$. \eparts \pr \points{??} The cookie monster is searching the supermarket for cookies. He does not know which aisle contains the cookies, and he can tell if an aisle has cookies if he peers down that aisle from the front of the store. Being a large monster (but dumb---he cannot read the signs), in one step he can move from the front of one aisle to the front of either adjacent aisle. He begins at aisle 0 (the center aisle) and follows the following search strategy. He first moves one step to the right to peer down aisle 1, then moves two steps to the left to peer down aisle~$-1$, then moves five step to the right to aisle~$4$ (inspecting the aisles in between as he moves), and in general going back and forth between aisle $m^2$ and aisle $-m^2$, for $m=1,2,3,\ldots$~\ We wonder how efficient this search strategy is---how many steps $s(n)$ the cookie monster takes if the cookies are in aisle~$n$. We are interested in asymptotic efficiency, for today's very large supermarkets: Find a simple expression $f(n)$ that is~$\Theta (s(n))$. \remove{ \pr \points{??} Let $A$ and $C$ be $n\times n$ matrices where $a_{i,j} = 1$ if city $j$ can be reached within a single day of air travel from city $i$, and $c_{i,j} = 1$ if city $j$ can be reached with a single day of car travel from city $i$. Otherwise entries are 0. Show how to compute a matrix $M$ where $m_{i,j} =1$ iff city $j$ can be reached from city $i$ by a single day of air travel followed by a single day of car travel. Also show how to compute $M'$ where $m'_{i,j} =1$ iff city $j$ can be reached from $i$ with 2 days of travel (at most) where each day is all car or all air. } \remove{ \pr \points{??} For each function $f(n)$ along the left side of the table below and each function $g(n)$ across the top, write $O$, $\Omega$, or $\Theta$ in the appropriate space, depending on whether $f(n)=O(g(n))$, $f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$. If there is more than one relation between $f(n)$ and $g(n)$, write only the strongest one. {\em Wrong answers will be penalized, so do not guess unless you are reasonably sure.} The first line is a demo solution. \[ \begin{array}{|c||c|c|c|} \hline & \hspace*{1in} & \hspace*{1in} & \hspace*{1in} \\ & n & n\lg n & n^2\\ & & & \\ \hline \hline & & & \\ 3n\lg n & \Omega & \Theta & O \\ & & & \\ \hline & & & \\ n^{0.99} \lg^2 n& & & \\ & & & \\ \hline & & & \\ 2n^2-5n\lg n& & & \\ & & & \\ \hline & & & \\ \lg(n!)& & & \\ & & & \\ \hline & & & \\ 3^{\lg n}& & & \\ & & & \\ \hline & & & \\ {\displaystyle \sum_{i=1}^n\lg i}& & & \\ & & & \\ \hline \end{array} \] } \end{problems} \end{document} \documentstyle[12pt]{article} \input{/a/class/6.042/spring94/handouts/macros-course} %\newcommand\npage{\vspace{.8in}} \newcommand\npage{\newpage} \setcounter{page}{0} \begin{document} \handout{quiz-2-sols}{Quiz 2 Solutions}{April 22, 1994} %\examinitials{Quiz 2 }{April 20, 1994} \begin{closeitemize} \item This quiz ends at 9 {\sc p.m.} It contains 8 problems. You have 120 minutes to earn 105 points. \item {\bf Initial the top of each page of your quiz. This is worth 5 points.} \item This quiz is closed book. You may use one $8\frac{1}{2}''\times 11''$ handwritten crib sheet. No calculators or electronic playback devices are permitted. \item Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Do not put part of the answer to one problem on the back of the sheet for another problem. \item Do not spend too much time on any problem. Read them all through first and attack them in the order that allows you to make the most progress. \item Show your work, as partial credit will be given. You will be graded not only on the correctness of your answer, but also on the {\bf clarity} with which you express it. {\bf Be neat.} \end{closeitemize} \renewcommand{\arraystretch}{.5} \begin{center} \begin{tabular}{|c|c|c|} \hline & &\hspace*{1in}\\ Problem&Points&Grade\\ & &\\ \hline \hline & &\\ Initials & 5 & \\ & &\\ \hline & &\\ 1 & 10 & \\ & &\\ \hline & &\\ 2 & 10 & \\ & &\\ \hline & &\\ 3 & 14 & \\ & &\\ \hline & &\\ 4 & 16 & \\ & &\\ \hline & &\\ 5 & 16 & \\ & &\\ \hline & &\\ 6 & 10 & \\ & &\\ \hline & &\\ 7 & 10 & \\ & &\\ \hline & &\\ 8 & 14 & \\ & &\\ \hline \hline & &\\ Total & 105 & \\ & &\\ \hline \end{tabular} \end{center} \renewcommand{\arraystretch}{1} \bigskip \bigskip \noindent Name:\ \mbox{}\hrulefill\mbox{}\par \newpage \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\npage%5 %\problem \points{10} How many orderings exist for a standard card %deck of $52$ cards if all the cards of the same suit are adjacent? % %You may leave your answer in terms of factorials and powers. % \npage%6 \problem \points{10} In how many ways can 6 men and 6 women be seated at a round table if men and women must sit in alternate seats? Since the table is round, rotating their positions does not count as a new seating arrangement. You need not simplify your answer---you may leave it in terms of factorials, powers, etc. %You may leave your answer in terms of factorials and powers. \npage%7 \problem \points{10} \begin{problemparts} \problempart What is the number of ways to distribute $n$ distinct toys among $k$ distinct children. There are no constraints on the number of presents a child can receive. \vspace{3in} \problempart How many ways could the toys be distributed if the toys were indistinguishable? \end{problemparts} \npage%8 \problem \points{14} \begin{problemparts} \problempart Use a combinatorial argument to prove that \[ \sum_{k=0}^n {r\choose k} {s \choose n-k} = {r+s\choose n} \] for all natural numbers $r,s,n$. \vspace{2.5in} \problempart Prove the same thing using the binomial theorem and the identity \[(1+x)^r (1+x)^s = (1+x)^{r+s}\quad.\] \end{problemparts} \npage%9 \problem \points{16} \begin{problemparts} \problempart What is the number of 11-combinations of the multiset \mbox{$S = \{\infty\cdot a, \; \infty\cdot b, \; \infty\cdot c, \; \infty\cdot d\}$?} (You need not simplify your answer---% you may leave it in terms of factorials, powers, etc.) \vspace{3in} \problempart Use inclusion-exclusion to determine the number of 11-combinations of the multiset $S = \{\infty\cdot a, \; 4\cdot b, \; 5\cdot c, \; 7\cdot d\}$. (You need not simplify your answer---% you may leave it in terms of factorials, powers, etc.) \end{problemparts} \npage%10 \problem \points{16} Let $a_n$ be the number of $n$-digit numbers composed of the digits $1,2,$ and $3$ such that the number of $1$'s is odd and the number of $2$'s is even. \begin{problemparts} \problempart Find the exponential generating function for the sequence $\langle a_0,a_1,a_2,\ldots\rangle$. \vspace{3.5in} \problempart Find a simple formula for $a_n$. \end{problemparts} \npage%1 \problem \points{10} Suppose you are playing a game that results in either a win or a loss. The outcomes of the games are mutually independent and you win each game with probability $2/3$. Suppose you play 7 times. What is the probability that you win exactly 3 out of the last 4 games? Describe the sample space and show your calculations. \npage%2 \problem \points{10} In a certain village, 20\% of the population has contracted disease $D$. When a person who has the disease is tested for it, he or she tests positive with probability~$9/10$. A person without $D$ tests positive for it with probability~$3/10$. If a villager is chosen uniformly at random and tests positive for $D$, what is the probability that he or she actually has the disease? (This is not a trick question---the probability is not 0 or 1.)\\ Describe the sample space and show your calculations. %\npage%3 %\problem \points{10} %Consider the following version of the Monty Hall game. %You are shown three doors. There is a prize behind %{\em two} of the doors, and a goat behind the other. %As usual, you pick a door. Now however Monty reveals %another door that has a prize behind it. He then offers you %the opportunity either to stick with what's behind the first %door you chose, or to switch and take what's behind the other %unopened door. % %Assume that Monty picks the doors for his prizes (and the %door he opens) at random. %What is the probability of winning if you play the switch %strategy. What is your probability of winning if you don't %switch. Show any necessary calculations. % \npage%4 \problem \points{14} Consider the experiment of tossing three fair coins. The probability for each coin to come up heads is $1/2$, and the results of the three flips are mutually independent. (For this problem you can use either definition of mutual independence that was given in class.) Let $A_1$ be the event that the first coin comes up heads. Let $A_2$ be the event that the first two coins come up the same (that is, they are either both heads or both tails). Let $A_3$ be the event that more coins come up heads than tails. Let $A_4$ be the event that the last coin is tails. \begin{problemparts} \problempart What is the sample space? \vspace{1.8in} \problempart What is the probability of each sample point? \vspace{1.8in} \problempart Calculate $\rm{Prob}[A_4 \mid A_2 \land A_3]$. \vspace{1.8in} \problempart %\points{} Are $A_1$ and $A_2$ independent? Justify your answer. \vspace{2.3in} \problempart Are $A_3$ and $A_4$ independent? Justify your answer. \vspace{2.3in} \problempart %\points{} Find 3 events (from $A_1,\ldots,A_4$) that are mutually independent. Justify your answer. \end{problemparts} % \npage%11 % \problem \points{10} Use generating functions to solve the recurrence % \[ a_n=\left\{ % \begin{array}{ll} % 0&\mbox{if $n=0$} \\ % 3&\mbox{if $n=1$} \\ % a_{n-1} + 2a_{n-2}&\hbox{for $n\ge2$}. \\ % \end{array} \right. \] % For partial credit, just find a simple expression for an ordinary generating % function for the sequence $\langle a_0,a_1,a_2,\ldots\rangle$. % % \npage%12 % \problem \points{10} Use the pigeonhole principle to prove that if % $m$ and $n$ are two positive integers then there exist distinct % natural numbers $i$ and $j$ such that $m^i-m^j$ is divisible by % $n$. % \end{problems} \end{document} \documentstyle[12pt]{article} \input{/a/class/6.042/spring94/handouts/macros-course} %\newcommand\npage{\vspace{.8in}} \newcommand\npage{\newpage} \setcounter{page}{0} \begin{document} \handout{quiz-2-sols}{Quiz 2 Solutions}{April 22, 1994} %\examinitials{Quiz 2 }{April 20, 1994} \begin{closeitemize} \item This quiz ends at 9 {\sc p.m.} It contains 8 problems. You have 120 minutes to earn 105 points. \item {\bf Initial the top of each page of your quiz. This is worth 5 points.} \item This quiz is closed book. You may use one $8\frac{1}{2}''\times 11''$ handwritten crib sheet. No calculators or electronic playback devices are permitted. \item Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Do not put part of the answer to one problem on the back of the sheet for another problem. \item Do not spend too much time on any problem. Read them all through first and attack them in the order that allows you to make the most progress. \item Show your work, as partial credit will be given. You will be graded not only on the correctness of your answer, but also on the {\bf clarity} with which you express it. {\bf Be neat.} \end{closeitemize} \renewcommand{\arraystretch}{.5} \begin{center} \begin{tabular}{|c|c|c|} \hline & &\hspace*{1in}\\ Problem&Points&Grade\\ & &\\ \hline \hline & &\\ Initials & 5 & \\ & &\\ \hline & &\\ 1 & 10 & \\ & &\\ \hline & &\\ 2 & 10 & \\ & &\\ \hline & &\\ 3 & 14 & \\ & &\\ \hline & &\\ 4 & 16 & \\ & &\\ \hline & &\\ 5 & 16 & \\ & &\\ \hline & &\\ 6 & 10 & \\ & &\\ \hline & &\\ 7 & 10 & \\ & &\\ \hline & &\\ 8 & 14 & \\ & &\\ \hline \hline & &\\ Total & 105 & \\ & &\\ \hline \end{tabular} \end{center} \renewcommand{\arraystretch}{1} \bigskip \bigskip \noindent Name:\ \mbox{}\hrulefill\mbox{}\par \newpage \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\npage%5 %\problem \points{10} How many orderings exist for a standard card %deck of $52$ cards if all the cards of the same suit are adjacent? % %You may leave your answer in terms of factorials and powers. % \npage%6 \problem \points{10} In how many ways can 6 men and 6 women be seated at a round table if men and women must sit in alternate seats? Since the table is round, rotating their positions does not count as a new seating arrangement. You need not simplify your answer---you may leave it in terms of factorials, powers, etc. %You may leave your answer in terms of factorials and powers. \npage%7 \problem \points{10} \begin{problemparts} \problempart What is the number of ways to distribute $n$ distinct toys among $k$ distinct children. There are no constraints on the number of presents a child can receive. \vspace{3in} \problempart How many ways could the toys be distributed if the toys were indistinguishable? \end{problemparts} \npage%8 \problem \points{14} \begin{problemparts} \problempart Use a combinatorial argument to prove that \[ \sum_{k=0}^n {r\choose k} {s \choose n-k} = {r+s\choose n} \] for all natural numbers $r,s,n$. \vspace{2.5in} \problempart Prove the same thing using the binomial theorem and the identity \[(1+x)^r (1+x)^s = (1+x)^{r+s}\quad.\] \end{problemparts} \npage%9 \problem \points{16} \begin{problemparts} \problempart What is the number of 11-combinations of the multiset \mbox{$S = \{\infty\cdot a, \; \infty\cdot b, \; \infty\cdot c, \; \infty\cdot d\}$?} (You need not simplify your answer---% you may leave it in terms of factorials, powers, etc.) \vspace{3in} \problempart Use inclusion-exclusion to determine the number of 11-combinations of the multiset $S = \{\infty\cdot a, \; 4\cdot b, \; 5\cdot c, \; 7\cdot d\}$. (You need not simplify your answer---% you may leave it in terms of factorials, powers, etc.) \end{problemparts} \npage%10 \problem \points{16} Let $a_n$ be the number of $n$-digit numbers composed of the digits $1,2,$ and $3$ such that the number of $1$'s is odd and the number of $2$'s is even. \begin{problemparts} \problempart Find the exponential generating function for the sequence $\langle a_0,a_1,a_2,\ldots\rangle$. \vspace{3.5in} \problempart Find a simple formula for $a_n$. \end{problemparts} \npage%1 \problem \points{10} Suppose you are playing a game that results in either a win or a loss. The outcomes of the games are mutually independent and you win each game with probability $2/3$. Suppose you play 7 times. What is the probability that you win exactly 3 out of the last 4 games? Describe the sample space and show your calculations. \npage%2 \problem \points{10} In a certain village, 20\% of the population has contracted disease $D$. When a person who has the disease is tested for it, he or she tests positive with probability~$9/10$. A person without $D$ tests positive for it with probability~$3/10$. If a villager is chosen uniformly at random and tests positive for $D$, what is the probability that he or she actually has the disease? (This is not a trick question---the probability is not 0 or 1.)\\ Describe the sample space and show your calculations. %\npage%3 %\problem \points{10} %Consider the following version of the Monty Hall game. %You are shown three doors. There is a prize behind %{\em two} of the doors, and a goat behind the other. %As usual, you pick a door. Now however Monty reveals %another door that has a prize behind it. He then offers you %the opportunity either to stick with what's behind the first %door you chose, or to switch and take what's behind the other %unopened door. % %Assume that Monty picks the doors for his prizes (and the %door he opens) at random. %What is the probability of winning if you play the switch %strategy. What is your probability of winning if you don't %switch. Show any necessary calculations. % \npage%4 \problem \points{14} Consider the experiment of tossing three fair coins. The probability for each coin to come up heads is $1/2$, and the results of the three flips are mutually independent. (For this problem you can use either definition of mutual independence that was given in class.) Let $A_1$ be the event that the first coin comes up heads. Let $A_2$ be the event that the first two coins come up the same (that is, they are either both heads or both tails). Let $A_3$ be the event that more coins come up heads than tails. Let $A_4$ be the event that the last coin is tails. \begin{problemparts} \problempart What is the sample space? \vspace{1.8in} \problempart What is the probability of each sample point? \vspace{1.8in} \problempart Calculate $\rm{Prob}[A_4 \mid A_2 \land A_3]$. \vspace{1.8in} \problempart %\points{} Are $A_1$ and $A_2$ independent? Justify your answer. \vspace{2.3in} \problempart Are $A_3$ and $A_4$ independent? Justify your answer. \vspace{2.3in} \problempart %\points{} Find 3 events (from $A_1,\ldots,A_4$) that are mutually independent. Justify your answer. \end{problemparts} % \npage%11 % \problem \points{10} Use generating functions to solve the recurrence % \[ a_n=\left\{ % \begin{array}{ll} % 0&\mbox{if $n=0$} \\ % 3&\mbox{if $n=1$} \\ % a_{n-1} + 2a_{n-2}&\hbox{for $n\ge2$}. \\ % \end{array} \right. \] % For partial credit, just find a simple expression for an ordinary generating % function for the sequence $\langle a_0,a_1,a_2,\ldots\rangle$. % % \npage%12 % \problem \points{10} Use the pigeonhole principle to prove that if % $m$ and $n$ are two positive integers then there exist distinct % natural numbers $i$ and $j$ such that $m^i-m^j$ is divisible by % $n$. % \end{problems} \end{document} \documentstyle[12pt,macpsfig,amssymb]{article} \input{/a/class/6.042/spring95/macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} %\newcommand{\pr}{\problem} \newcommand{\pr}{\newpage\problem} \renewcommand{\bparts}{\begin{testproblemparts}} \renewcommand{\eparts}{\end{testproblemparts}} \begin{document} \examinitials{Quiz 2}{April 25, 1995} \begin{closeitemize} \item This quiz is open book. \item Put your name on the top of each page---the pages of this booklet will be separated for grading. \item Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Please do not put part of the answer to one problem on the back of the sheet for another problem. \item Do not spend too much time on any problem. Read them all through first and attack them in the order that allows you to make the most progress. \item Show your work, as partial credit will be given. You will be graded not only on the correctness of your answer, but also on the clarity with which you express it. {\bf Be neat}. \item This quiz ends at 9 {\sc p.m.} It contains six problems. The problems are 16 points each, and you will get 4 points for writing your name, tutorial TA and time clearly. \item GOOD LUCK! \end{closeitemize} \bigskip \bigskip \renewcommand{\arraystretch}{.5} \begin{center} \begin{tabular}{|c|c|c|} \hline & &\hspace*{1in}\\ Problem&Points&Grade\\ & &\\ \hline \hline & &\\ name & 4 & \\& &\\ \hline & &\\ 1 & 16 & \\& &\\\hline & &\\ 2 & 16 & \\& &\\\hline& &\\ 3 & 16 & \\& &\\\hline& &\\ 4 & 16 & \\& &\\\hline& &\\ 5 & 16 & \\& &\\\hline& &\\ 6 & 16 & \\& &\\ \hline \hline & &\\ Total & 100 & \\ & &\\ \hline \end{tabular} \end{center} \renewcommand{\arraystretch}{1} \bigskip \bigskip \bigskip \noindent Name:\ \mbox{}\hrulefill\mbox{}\par \bigskip \bigskip \noindent Please circle your tutorial TA: \hspace{.7in} Jennifer \hspace{.7in} Parry \hspace{.7in} Steve \hspace{.7in} Ravi \bigskip \bigskip \noindent Please circle your tutorial time: \hspace{.5in} 10 \hspace{.5in} 11 \hspace{.5in} 12 \hspace{.5in} 1 \hspace{.5in} 2 \hspace{.5in} 3 \newpage \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \pr \points{16} Prove that if \[\Lambda \cup \{\psi\} \models \chi \mbox{ and } \Lambda \cup \{\phi\} \models \chi \mbox{ and } \Lambda \models \psi\vee \phi \] then \[ \Lambda \models \chi \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \pr \points{16} %Prove or disprove: %$f(n)=O(g(n))$ implies $\lg(f(n)) = O(\lg(g(n)))$, where $\lg(g(n)) > 0$ and %$f(n) \geq 1$ for all sufficiently large $n$. Prove or disprove: $f(n)=O(g(n))$ implies $\lg(f(n) = O(\lg(g(n)))$, where $g(n)$ is nondecreasing, $g(1) > 1$ and $f(n) \geq 0$ for all sufficiently large $n$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \pr \points{16} Solve the following recurrence: \[ f(1)=f(2)=1 \] \[ f(n)-4(n-1)+4(n-2) = 3^n \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \pr \points{16} Give tight ($\Theta$) bounds for $T(n)$. Assume that $T(n)$ is constant for $n \leq 2$. \bparts \ppart $T(n) = 7T(n/3) + n^2$ \bigskip \bigskip \bigskip \ppart $T(n) = T(2n/3) + T(n/4) + n$ \bigskip \bigskip \bigskip \ppart $T(n) = 4T(n/3) + n$ \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \pr \points{16} \bparts \ppart How many ways are there to color $n$ (distinguishable) balls using exactly $k$ colors? (Use no more and no fewer than $k$ colors) \bigskip \bigskip \bigskip \ppart If $x > k$ colors are available, how many ways are there to color the $n$ balls using exactly $k$ of those colors? \bigskip \bigskip \bigskip \ppart Prove that \[ x^n = \sum_{k=1}^n S(n,k)\cdot x(x-1)\cdots(x-k+1) \] by showing that the two sides agree for any positive integer $x$. ($S(n,k)$ is the Stirling number of the second kind.) \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \pr \points{16} How many permutations of ABCDEFG are there that don't contain ``$\cdots$BEG$\cdots$'' or ``$\cdots$AD$\cdots$''? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{problems} \end{document} \documentstyle[12pt,macpsfig,psfig,amssymb]{article} \input{macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} %\newcommand{\pr}{\problem} \begin{document} \qsol{1}{October 13, 1995} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %1 \problem \bparts \ppart Use Euclid's algorithm to find the $gcd$ of $241$ and $178$. \bigskip $ \begin{array}{lccrr} & 241 & 178 & 65 & -88 \\ 1 & 178 & 63 & -25 & 65 \\ 2 & 63 & 52 & 19 & -23 \\ 1 & 52 & 11 & -4 & 19 \\ 4 & 11 & 8 & 3 & -4 \\ 1 & 8 & 3 & -1 & 3 \\ 2 & 3 & 2 & 1 & -1 \\ 1 & 2 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 & 0 \end{array}$ Hence, $gcd(241,178) = 1$. \ppart Find an integer solution to $241x + 178y = 10.$ \bigskip From part a) we have \[ gcd(241,178) = 65\cdot 241 - 88\cdot 178 = 1.\] Multiplying by $10$ we get \[ 650\cdot 241 - 880\cdot 178 = 10.\] Hence, one solution is $x = 650$ and $y = -880.$ \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %2 \problem Let $S$ be a set of $n$ positive integers. For any subset $A \subset S$ let $\Sigma(A)$ denote the sum of the elements in $A$. You are given that $\Sigma(S) \leq 2^n - 2.$ \bparts \ppart Prove that there exist two distinct non-empty sets $A$ and $B$ such that $\Sigma(A) = \Sigma(B)$. \bigskip \begin{proof} Consider ${\cal C} = {\cal P}(S) - \{S,\phi\}$. This is the collection of all nonempty subsets of $S$, excluding $S$. $|{\cal C}| = 2^n -2$. For any $A \in {\cal C}$ it is the case that $1 \leq \Sigma(A) \leq 2^n - 3$. It is clear that $1 \leq \Sigma(A)$ since $S$ is a set of positive integers and $A$ is a nonempty subset of it. It is also clear that $\Sigma(A) \leq 2^n - 3$, since $A$ is a proper subset of $S$ and hence $\Sigma(A) < \Sigma(A) \leq 2^n - 2$. Thus we have $2^n-2$ elements $A$ in ${\cal C}$ such that $1 \leq \Sigma(A) \leq 2^n - 3$. By the pigeonhole principle, we have that there exist two sets $A, B \in {\cal C}$ such that $\Sigma(A) = \Sigma(B)$. By construction we have that $A$ and $B$ are distinct non-empty subsets of $S$. \end{proof} \ppart Prove that there exist two distinct non-empty sets $A$ and $B$ such that $\Sigma(A) = \Sigma(B)$ and $A \cap B = \phi.$ \bigskip \begin{proof} Let $A'$ and $B'$ be the two sets from part a). It is the case that $A' \not\subset B'$ and $B' \not\subset A'$ because for any two sets $P,Q \subset S$ it is the case that $P \subset Q \Rightarrow \Sigma(P) < \Sigma(Q)$. Now consider, $A = A' - A' \cap B'$ and $B = B' - A' \cap B'$. It is clear that $\Sigma(A) = \Sigma(B)$ and $A \cap B = \phi.$ Hence we are done. \end{proof} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %3 \problem \points{20} Let $(a,b) \sim (c,d)$ if $a+d = b+c$. \bparts \ppart \points{10} Prove that $\sim$ is an equivalence relation on $\integers \times \integers$. \bigskip \begin{itemize} \item {\em Reflexivity} $(a,b) \sim (a,b)$ since $a + b = b + a$. \item {\em Symmetry} $(a,b) \sim (c,d) \Rightarrow (c,d) \sim (a,b)$ since $a + d = b + c \Rightarrow c + b = d + a$. \item {\em Transitivity} Assume $(a,b) \sim (c,d)$, i.e. $ a + d = b + c$. And, $(c,d) \sim (e,f)$, i.e. $c + f = d + e$. Adding we get $a + d + c + f = b + c + d + e$ or $a + f = b + e$, i.e. $(a,b) \sim (e,f)$. Hence $(a,b) \sim (c,d) \wedge (c,d) \sim (e,f) \Rightarrow (a,b) \sim (e,f)$. \end{itemize} Since $\sim$ is reflexive, symmetric and transitive it is an equivalence relation. \ppart Partition the set $\{0,1,2\} \times \{0,1,2\}$ into the distinct equivalence classes under $\sim$. \bigskip We can rewrite $(a,b) \sim (c,d)$ if $a+d = b+c$ as $(a,b) \sim (c,d)$ if $a-b = c -d$. This shows that with any equivalence class ${\cal C}$ we can associate a {\em difference} $d$ such that $(a,b) \in {\cal C} \Rightarrow a - b = d$. This gives us an easy way to list the equivalence classes of $\{0,1,2\} \times \{0,1,2\}$. \begin{itemize} \item $d = -2$ : $\{(0,2)\}$. \item $d= -1$ : $\{(0,1),(1,2)\}$. \item $d= 0$ : $\{(0,0),(1,1),(2,2)\}$. \item $d= 1$ : $\{(1,0),(2,1)\}$. \item $d= 2$ : $\{(2,0)\}$. \end{itemize} \ppart How many distinct equivalence classes under $\sim$ are there on the set $\{0,1,\ldots, n\} \times \{0,1,\ldots, n\}$. You do not need to prove your answer. \bigskip $2n+1$ since the difference can be any value in $\{-n,\ldots, n\}$. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %4 \problem Prove by induction that \[ {\displaystyle \sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2}.\] \bigskip Let $P(n)$ be ``${\displaystyle \sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2}.$''\\ {\em Base case.} $P(1)$ is true since ${\displaystyle \sum_{i=1}^1 i^3 = 1 = \left(\sum_{i=1}^1 i\right)^2}$. \\ {\em Inductive step.} Assume $P(n)$ is true. Then \[ {\displaystyle \sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2}.\] Adding $(n+1)^3$ to both sides we get, $ \begin{array}{lccr} {\displaystyle \sum_{i=1}^{n+1} i^3} & = &\left({\displaystyle \sum_{i=1}^n i}\right)^2 + (n+1)^3 & \\ & = & (n(n+1)/2)^2 + (n+1)^3 & \mbox{since ${\displaystyle \sum_{i=1}^n i} = n(n+1)/2$} \\ & = &(n+1)^2/4 \times (n^2 + 4(n+1)) & \\ & = &((n+1)(n+2)/2)^2 & \\ & = & \left({\displaystyle \sum_{i=1}^{n+1} i}\right)^2 \end{array}$ Hence, $P(n+1)$ is true. Thus $P(n)$ is true for all $n$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %5 \problem $n$ teams play a tournament. Every team plays every other team exactly once and all games end in a win/loss. It is possible that weaker teams can beat stronger teams. \bparts \ppart Any tournament can be viewed as a relation on the set of teams, with $(A,B)$ in the relation iff $A$ beats $B$. Is this relation a partial order for all tournaments? If yes, prove it. If not list all partial order properties that can fail. \bigskip Reflexivity fails since $(A,A)$ does not belong to the relation of the tournament. Transitivity can fail since it could be in a tournament that $A$ beats $B$ who beats $C$ who in turn beats $A$, i.e. $(A,B)$ and $(B,C)$ could be in the relation of the tournament without there also being $(A,C)$. (Note that anti-symmetry holds vacuously, since we never have both $(A,B)$ and $(B,A)$ in the relation.) \ppart Show (by induction) that in any tournament there exists a two-step champion, i.e. there exists a team $A$ such that for every other team $B$ \\ \[ \mbox{it is the case that } \left\{ \begin{array}{l} \mbox{ $A$ has beaten $B$, or} \\ \mbox{ there exists $C$ such that $A$ has beaten $C$ who has beaten $B$.} \end{array} \right. \] \bigskip \begin{proof} Let $P(n)$ be ``in any tournament with $n$ teams there exists a two-step champion.'' \\ {\em Base case.} $P(2)$ is true since in a tournament with only two teams the winner is a two-step champion. \\ {\em Inductive step.} Assume $P(n)$ is true. Consider a tournament with $n+1$ teams numbered $1, 2, \ldots, n+1$. Then the games between teams $1, 2, \ldots, n$ forms a subtournament and hence, by the inductive hypothesis, it must be the case that this subtournament possesses a two-step champion. Let this two-step champion be the team numbered $1$ without loss of generality. Now, if $n+1$ loses to $1$ or any of the teams that lost to $1$ then it is clear that $1$ is a two-step champion for the whole tournament. Otherwise, it is the case that $n+1$ beat $1$ and all the teams that lost to $1$ which makes $n+1$ the two-step champion. In either case the tournament possesses a two-step champion. Thus $P(n+1)$ is true. Hence $P(n)$ is true for all $n$. \end{proof} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %6 \problem \bparts \ppart Show that the set of real numbers $\in (0,1)$ that have only $3$s and $7$s in their decimal representation is uncountable. \bigskip \begin{proof} Suppose the set ${\cal C}$ of real numbers $\in (0,1)$ that have only $3$s and $7$s in their decimal representation is countable. Then there exists a bijection $f: \naturals \rightarrow {\cal C}$. Represent this by a matrix $M$ where $M_{ij} = 3$ if the $j$th digit of $f(i)$ (after the decimal point) is $3$, and $M_{ij} = 7$ otherwise. Now create a new number $T$ by considering the diagonal elements $M_{ii}$ of the matrix. $i$th digit of $T = 3$ if $M_{ii} = 7$, otherwise $i$th digit of $T = 7$. This is a valid element of ${\cal C}$ and $f^{-1}(T)$ must exist. But observe that if the $f^{-1}(T)$th digit of $f^{-1}(T)$ is $3$ then the $f^{-1}(T)$th digit of $f^{-1}(T)$ must be $7$ and vice-versa. Thus, either way, we have a contradiction. Hence ${\cal C}$ cannot be countable. \end{proof} \ppart Prove that the cross product of two countable sets is countable. \bigskip \begin{proof} Let the two sets be $A = \{a_1,a_2,\ldots\}$ and $B = \{b_1, b_2,\ldots\}$. We can list the elements of the sets in this fashion because they are countable and hence have a bijection with the naturals. We list the cross product, using the idea of dove-tailing shown in class, to get the listing $\{ (a_1,b_1),(a_1,b_2),(a_2,b_1),(a_1,b_3),(a_2,b_2), (a_3,b_1), \ldots \}$. It is easy to see that $(a_i,b_j)$ will occur before position $(i+j)^2$ in our listing. Since we have been able to give a valid listing $A \times B$ is countable. \end{proof} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \iffalse %7 \pr \points{20} The following poset shows the ``prerequisite'' dependencies among the computer science courses required for an M.Eng degree at MIT. (It is not factually accurate.) The dependencies go upwards. \begin{figure}[htbp] \centerline{\psfig{figure=course6.ps,height=2in}} \caption{A poset of course 6 prerequisite dependencies} \label{fig:inter} \end{figure} \bparts \ppart Given that there is no limit to the number of courses an MIT student can take in a term, what is the minimum number of terms needed for an MIT student to to get a course 6 M.Eng degree. \ppart Harvard students are allowed to enroll for at most two courses a term at MIT. What is the minimum number of terms a Harvard student will take to get a course 6 M.Eng degree. \eparts \fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{problems} \end{document} \documentstyle[12pt,twoside]{article} \input{macros-course} \begin{document} \handout{quiz-information}{Quiz Information}{September 26, 1995} \noindent\begin{center} {\Large\bf QUIZ 1} \vspace*{.2in} \underline{When:} {\large October 11, Wednesday, 7:00 to 9:00 PM} \vspace*{.2in} \underline{Where:} {\large 10-250} \vspace*{.2in} \underline{Crib Sheet:} {\large The quiz is not open-book, but you are allowed to bring one sheet to the exam. You may have whatever information you like on it but it must be handwritten and must not be xeroxed.} \vspace*{.2in} \underline{Syllabus:} {\large Everything done until and including the recitation on October 6} \vspace*{.2in} \underline{Make-up Exam:} {\large If you have a conflict come see us NOW} \vspace*{.2in} \underline{Special office hours:} {\large There will be special office hours during quiz-week. Your TAs will give you details next week.} \end{center} \end{document} \documentstyle[12pt,twoside]{article} \input{macros-course} \begin{document} \handout{quiz-information2}{Quiz Information}{November 2, 1995} \noindent\begin{center} {\Large\bf QUIZ 2} \vspace*{.2in} \underline{When:} {\large November 15, Wednesday, 7:00 to 9:00 PM} \vspace*{.2in} \underline{Where:} {\large 10-250} \vspace*{.2in} \underline{Crib Sheet:} {\large The quiz is not open-book, but you are allowed to bring two sheets to the exam. You may have whatever information you like on it but it must be handwritten and must not be xeroxed.} \vspace*{.2in} \underline{Syllabus:} {\large Everything done from the beginning until and including the tutorial on November 13. But the emphasis will be on stuff done after Quiz 1.} \vspace*{.2in} \underline{Make-up Exam:} {\large If you have a conflict come see us NOW} \vspace*{.2in} \underline{Special office hours:} {\large There will be special office hours during quiz-week. Your TAs will give you details next week. We will also be handing out a practice quiz.} \end{center} \end{document} \documentstyle[12pt,twoside]{article} \input{macros-course} \begin{document} \handout{quiz-information3}{Quiz Information}{November 28, 1995} \noindent\begin{center} {\Large\bf QUIZ 3} \vspace*{.2in} \underline{When:} {\large December 06, Wednesday, 7:00 to 9:00 PM} \vspace*{.2in} \underline{Where:} {\large 10-250} \vspace*{.2in} \underline{Crib Sheet:} {\large The quiz is not open-book, but you are allowed to bring two sheets to the exam. You may have whatever information you like on it but it must be handwritten and must not be xeroxed.} \vspace*{.2in} \underline{Syllabus:} {\large Everything done from the beginning until and including the lecture on December 05. But the emphasis will be on stuff done after Quiz 2.} \vspace*{.2in} \underline{Make-up Exam:} {\large If you have a conflict come see us NOW} \vspace*{.2in} \underline{Special office hours:} {\large There will be special office hours during quiz-week. Your TAs will give you details next week.} \end{center} \end{document} \documentstyle[12pt,macpsfig,psfig,amssymb]{article} \input{macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} %\newcommand{\pr}{\problem} \begin{document} \qsol{2}{November 16, 1995} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %1 \problem \bparts \ppart Give tight ($\Theta$) bounds for \[{\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}}.\] \bigskip \begin{eqnarray*} {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\ {\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\ 2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\ {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 1}{\sqrt{n}}} \\ 2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\ \end{eqnarray*} That is \[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\] \ppart Express the following in closed form \[ {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q}.\] (Note that the lower indices are not constants.) \bigskip \begin{eqnarray*} {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q} & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{q=p}^{\infty} y^{q-p}} & \\ & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{r=0}^{\infty} y^r} & \\ & = {\displaystyle \left( \sum_{p=1}^{\infty} x^py^p \right) \left( \sum_{r=0}^{\infty} y^r \right)} & \\ & = \left( \frac{xy}{1-xy}\right)\left( \frac{1}{1-y}\right). \end{eqnarray*} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %2 \problem I have $n$ one-dollar bills that I wish to donate to $m$ charities. \bparts \ppart In how many ways can I do this if I don't care how much each charity gets? \bigskip Simply insert $m-1$ bars into a string of $n$ one-dollar bills. Then the $i$-th charity gets the money between bars $i-1$ and $i$. This gives you ${n+m-1 \choose m-1 } $ ways to distribute the money. \ppart In how many ways can I do this so that each charity gets at least \$ $10$? \bigskip First give 10 dollars to each charity, then distribute the remaining $n-10m$ dollars as in part a. This gives you ${n+m-1-10m \choose m-1}= {n-9m-1 \choose m-1}$ ways as long as $n\geq 10m$. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %3 \problem In how many ways can $5$ indistinguishable covered wagons, $4$ indistinguishable uncovered wagons and $1$ horse be arranged in a circle? \bigskip This problem is just a permutation of a multiset, except that we need to account for rotations of a circle being the same. This can be thought of either as fixing one object, say the horse, and arranging the wagons around it (${9\choose 5}$ ways), or counting the permutations and dividing by $10$ to avoid overcounting the rotations ($\frac{1}{10}\frac{10!}{5!4!1!}$). Either way the answer is 126. The most common mistake was to forget about overcounting the rotations. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %4 \problem How many $6$-digit decimal numbers are there that do not contain ``$123$'' or ``$456$'' as a subsequence? (for purposes of this problem numbers may have leading $0$'s) \bigskip Let \begin{itemize} \item $A$ be the set of all six-digit strings, using the digits $\{0, 1, \ldots, 9\}$. \item $B$ be the set of six-digit strings that contain the subsequence $123$. \item $C$ be the set of all six-digit strings that contain the subsequence $456$. \item $D$ be the set of all six-digit strings that do not contain $123$ or $456$. \end{itemize} We're interested in figuring out $| D |$. Since $$D = A - (B \cup C),$$ and $B \cup C \subseteq A$, we can use the inclusion-exclusion formula: $$| D | = | A | - |B \cup C| = | A | - | B | - | C | + | B \cap C |.$$ First, $|A| = 10^6$, since we can put any of ten digits in each of six places. Now, a string can contain $123$ in any of four positions; once this position is chosen, we have $1000$ choices for the remaining positions. However, this approach counts the string $123123$ twice, so the total size of $B$ is $$| B | = 4(1000) - 1 = 3999.$$ By the same reasoning, we get $$| C | = 3999.$$ Finally, there are only two strings in $B \cap C$, namely $123456$ and $456123$. Thus, $$| B \cap C | = 2.$$ Plugging this into our formula, we get $$| D | = 10^6 - 3999 - 3999 + 2 = 992004.$$ {\em (Common Mistakes: A lot of people forgot about the double-counting of $123123$ and $456456$, and so had $|B| = |C| = 4000$. Some people also argued that since $123$ can appear in one of only four places in the string, $|B| = 4$.)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %5 \problem Consider the following nuclear reaction. There is one particle of type $1$ at time instant $1$. Each particle of type $i$ existing at time $t$ undergoes fission to produce one particle of type $i+1$ and one of type $i+2$ at time instant $t+1$. \bparts \ppart Write and justify a recurrence for $f(i,t)$, the number of particles of type $i$ at time $t$. (Make sure to include the base cases for your recurrence.) \bigskip Particles of types $i-2$ and $i-1$ at time $t-1$ give rise to particles of type $i$ at time $t$ and this is the only way that particles of type $i$ are formed at time $t$. Hence we get the recurrence \[ f(i,t) = f(i-1,t-1) + f(i-2,t-1), t > 1. \] The base case is \begin{itemize} \item $f(1,1) = 1$. \item $f(i,1) = 0, -\infty \leq i \leq \infty, i \not= 1$. \end{itemize} \ppart Prove by induction that $f(i,t) = {t-1\choose i-t}$. (You do not need to reprove identities that were proven in class.) \bigskip (Note: Let $a$ be any nonnegative integer and $b$ be any integer. In what follows, we use the definition that ${a\choose b} = \frac{a!}{b!(a-b)!}$ when $a\geq b \geq 0$ and otherwise ${a\choose b} = 0$ when . Pascal's identity holds for this definition.) The proof is by induction on $t$. Let $P(t)$ be \[f(i,t) = {t-1\choose i-t}, \forall i.\] Base Case. $P(1)$ is true since \begin{itemize} \item $f(1,1) = {0\choose 0} = 1$. \item $f(i,1) = {0\choose i-1} = 0, -\infty \leq i \leq \infty, i \not= 1$. \end{itemize} Inductive step. Assume $P(t)$ is true. Consider $P(t+1)$. \begin{eqnarray*} f(i,t+1) & = f(i-1,t) + f(i-2,t) & \mbox{ by the recurrence from part a)}\\ & = {t-1\choose i-1-t} + {t-1\choose i-2-t} & \mbox{ by inductive hypothesis} \\ & = {t\choose i-1-t} & \mbox{ by Pascal's identity} \end{eqnarray*} Hence $P(t+1)$ is true. Thus $P(t)$ is true for all $t$ and we are done. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %6 \problem \bparts \ppart Give tight ($\Theta$) bounds for $T(n)$. Assume that $T(n)$ is constant for $n \leq 10$. \[T(n) = 4T(n/2) + 6n.\] \bigskip \begin{eqnarray*} T(n) & = 4T(n/2) + 6n & \\ & = 4^2T(n/2^2) + 6(n + n/2) & \\ & = \ldots & \\ & = 4^iT(n/2^i) + 6(n + n/2 + \ldots + n/2^{i-1}) & \\ & = \ldots & \\ & = 4^{\log_2 n}T(1) + 6(n + n/2 + \ldots + n/2^{\log_2 n \ -1}) & \\ & = n^2T(1) + O(n) & \\ & = \Theta(n^2) \end{eqnarray*} \ppart \points{10} Rank the following functions by order of growth; that is find an arrangement $g_1 = \alpha(g_2) = \alpha(g_3) = \ldots = \alpha(g_6)$ and state whether $\alpha$ is $o$ or $\Theta$ for each step. \begin{itemize} \item $n(\log_2 n)^5$ \item $n^3$ \item $n!$ \item $(n!)^2$ \item $n^n$ \item $3\cdot 8^{\log_2 n} + 4^{\log_2 n}$ \end{itemize} \bigskip \[ n(\log_2 n)^5 = o(n^3) = \Theta(3\cdot 8^{\log_2 n} + 4^{\log_2 n}) = o(n!) = o(n^n) = o((n!)^2). \] \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %7 \problem \bparts \ppart Let $p_k$ be the number of ways to make change of $k$ cents with indistinguishable pennies ($1$-cent coins). Give an ordinary generating function for $p_k$. \bigskip \[\frac{1}{1-x}.\] \ppart Let $n_k$ be the number of ways to make change of $k$ cents with indistinguishable nickels ($5$-cent coins). Give an ordinary generating function for $n_k$. \bigskip \[\frac{1}{1-x^5}.\] \ppart Let $s_k$ be the number of ways to make change of $k$ cents with indistinguishable pennies or nickels. Give an ordinary generating function for $s_k$. \bigskip \[\left( \frac{1}{1-x}\right) \left( \frac{1}{1-x^5} \right). \] \ppart Give an ordinary generating function for the number of ways to make change of $k$ cents with at least $3$ nickels and an odd number of pennies. (this part may be a little hard so don't knock yourself out trying to solve it.) \bigskip \[\left( \frac{x^{15}}{1-x^5}\right) \left( \frac{x}{1-x^2} \right). \] \eparts \end{problems} \end{document} \documentstyle[12pt,macpsfig,psfig,amstex,amssymb]{article} \input{macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} %\newcommand{\pr}{\problem} \begin{document} \qsol{3}{December 6, 1995} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %1 \problem Suppose I roll two independent standard dice and subtract the smaller value from the larger value. \bparts \ppart What is the probability distribution for the resulting difference? (i.e. give the probability of getting the result $k$ for all $k$) Let $R$ be the random variable that is the larger die roll minus the smaller die roll. The easiest way to see the probability distribution of $R$ is to make a table of the 36 outcomes and see what the value of the larger minus the smaller is. \begin{tabular}{c|c|c|c|c|c|c|} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 2 & 1 & 0 & 1 & 2 & 3 & 4 \\ \hline 3 & 2 & 1 & 0 & 1 & 2 & 3 \\ \hline 4 & 3 & 2 & 1 & 0 & 1 & 2 \\ \hline 5 & 4 & 3 & 2 & 1 & 0 & 1 \\ \hline 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ \hline \end{tabular} Since these entries are all equally likely, the probability $R=k$ is just the number of entries that are $k$ divided by 36. \begin{align*} Pr(R<0) &= 0 \\ Pr(R=0) &= \frac{6}{36} = \frac{1}{6}\\ Pr(R=1) &= \frac{10}{36} = \frac{5}{18}\\ Pr(R=2) &= \frac{8}{36} = \frac{2}{9}\\ Pr(R=3) &= \frac{6}{36} = \frac{1}{6}\\ Pr(R=4) &= \frac{4}{36} = \frac{1}{9}\\ Pr(R=5) &= \frac{2}{36} = \frac{1}{18}\\ Pr(R>5) &= 0 \end{align*} \ppart What is the mean of the result? The mean is \begin{align*} E[R] &= \sum_{k=0}^5 k Pr(R=k) \\ &= (1)\frac{6}{36} + (2)\frac{10}{36} + (3)\frac{8}{36}+(4)\frac{6}{36}+(5)\frac{4}{36}+(6)\frac{2}{36} \\ &= \frac{70}{36} \\ &= \frac{35}{18} \end{align*} \ppart What is the variance of the result? The variance is $E[R^2] -(E[R])^2$. \begin{align*} E[R^2] &= \sum_{k=0}^5 k^2 Pr(R=k) \\ &= (1^2)\frac{6}{36} + (2^2)\frac{10}{36} + (3^2)\frac{8}{36}+(4^2)\frac{6}{36}+(5^2)\frac{4}{36}+(6^2)\frac{2}{36}\\ &= \frac{210}{36} \\ &= \frac{105}{18} \\ E[R] &= \frac{35}{18} \;\;\;\; {\rm(from\;part\;b)} \end{align*} So the variance is $$ \frac{105}{18} - \left( \frac{35}{18} \right)^2 = \frac{665}{324} $$ \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %2 \problem Suppose I roll two independent standard dice, and consider the following three events: \begin{itemize} \item the first die is odd \item the second die is odd \item the sum of the dice is odd \end{itemize} \bparts \ppart Show these events are pairwise independent. Let $A,B$ and $C$ denote the first second and third events respectively. The first and the second events are independent by definition: $P(A)=P(B)=1/2=P(A|B).$ The first and the third events are independent because given the first die is odd the sum is odd if and only if the second die is even, an event which happens with probability 1/2. Thus $P(C|A)=1/2.$ On the other hand, the unconditional probability of the third event is 1/2, too. Indeed: $P(C)=P(A)P(\bar{B})+ +P(\bar{A})P(B)=1/4+1/4=1/2.$ Thus $P(C)=P(A|C)$ as claimed. An identical argument shows that $B$ and $C$ are independent. \ppart Are they mutually independent? Why, or why not? $A, B$ and $C$ are not mutually independent since $P(A)P(B)P(C)=(1/2)^3=(1/8)$ whereas $P(A\cap B\cap C)=0$. (Indeed: if both dice are odd, the sum is necessarily even). \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %3 \problem There is a bag with $999$ regular nickels and $1$ two-headed nickel. Experiment X1 consists of pulling a coin out of the bag at random and flipping it once before putting it back in. \bparts \ppart You perform X1 once. What is the probability you get 1 head? The probability is $$\frac{999}{1000} \cdot \frac{1}{2} + \frac{1}{1000} \cdot 1 = \frac{1001}{2000}.$$ \ppart You repeat X1 10 times (i.e. you pull a coin out, flip it and put it back in, repeating the whole process 10 times). What is the probability you get 10 heads? Since the experiments are independent, the probability is $$\left( \frac{1001}{2000} \right)^{10}.$$ \ppart You repeat X1 10 times. What is the most likely number of heads you get, i.e. for which $k$ is the probability of getting $k$ heads maximized? (Justify your answer) The distribution of heads is binomial, with success probability $p = \frac{1001}{2000}$. Thus, by taking ratios of $Pr(X = k-1)$ to $Pr(k)$ for increasing values of $k$ as in class, we see that the probability increases for $k \leq np = \frac{5005}{1000}$, and then decreases. Thus the most likely outcome is $5$. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem There is a bag with $999$ regular nickels and $1$ two-headed nickel. Experiment X2$(k)$ consists of pulling a coin out of the bag at random and then flipping the same coin $k$ times before putting it back. \bparts \ppart You perform X2$(10)$. What is the probability you get 10 heads? Let $A$ be the event you draw the two-headed nickel and $B$ be the event you get 10 heads in a row. Then, \begin{eqnarray*} Pr(B) & = & Pr(B \wedge A) + Pr(B \wedge \overline{A}) \\ & = & Pr(B|A) Pr(A) + Pr(B|\overline{A})Pr(\overline{A}) \\ \end{eqnarray*} Clearly, $Pr(A) = 1/1000$ and $Pr(B) = 999/1000$. If you get the two-headed nickel, you will get all heads, so $Pr(B|A) = 1$. The probability of getting ten heads with the fair nickel is $2^{-10}$. Thus, $Pr(B|\overline{A})=2^{-10}$. Therefore, \[ Pr(B) = \frac{1}{1000} + \frac{999}{1000}2^{-10} =\frac{2023}{1024000} \] \ppart You perform X2$(10)$. Given that you get $10$ heads what is the probability that you pulled out the two-headed coin? \[ Pr(A|B) = \frac{Pr(A \wedge B)}{Pr(B)} \] We have $Pr(B)$ from (a). $Pr(A \wedge B) = 1/1000$, since if we draw the two-headed nickel, we will get all heads. Thus, \[ Pr(A|B) = \frac{1/1000}{2023/1024000} = \frac{1024}{2023} \] \ppart You perform X2$(10)$. Given that you get $10$ heads what is the probability that another $10$ flips with the coin you pulled out will all come up heads? Let $C$ be the event that the next 10 flips are heads. There are two ways to do this problem. Method 1: Note that the event $C\wedge B$ is equivalent to getting 20 heads in a row. \begin{eqnarray*} Pr(C|B) &=& \frac{Pr(C\wedge B)}{Pr(B)} \\ &=& \frac{Pr(\mbox{20 heads} )}{Pr(\mbox{10 heads})} \\ &= & \frac{\frac{1}{1000} + \frac{999}{1000}2^{-20}} {\frac{1}{1000} + \frac{999}{1000}2^{-10}} \\ &=& \frac{1,049,575}{2,071,552} \end{eqnarray*} Method 2: \begin{eqnarray*} Pr(C|B) &=& Pr(C \wedge A|B) + Pr(C \wedge \overline{A}|B) \\ &=& Pr(C|A\wedge B)Pr(A|B) + Pr(C|\overline{A} \wedge B) Pr(\overline{A}|B) \\ \end{eqnarray*} In (b), we determined $Pr(A|B)$. $Pr(\overline{A}|B) = 1- Pr(A|B)$. Now, $Pr(C|A\wedge B) = 1$, since the coin is two headed. $Pr(C|\overline{A} \wedge B) = 2^{-10}$, since the flips are independent. Therefore, \[ Pr(C|B) = \frac{1024}{2023} + \left(1-\frac{1024}{2023}\right) 2^{-10} = \frac{1,049,575}{2,071,552} \] \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem A space station can tolerate up to $k$ meteor hits in its lifetime. Each year there is a probability $p$ that it gets hit by exactly one meteor and probability $1-p$ that it gets hit by none. \bparts \ppart What is the probability $P(n)$ that the space-station survives exactly $n$ years, i.e. the $k$'th meteor hits the space-station in year $n$? In order for the space station to survive exactly $n$ years, we have to have the $k^{th}$ meteor hit at year $n$. This can be rephrased in terms of two independent events. Let $S$ be the event that the space station survives exactly $n$ years. Let $M$ be the number of meteor strikes in years $1,\ldots,n-1$. Let $A$ be the event that a meteor hits in year $n$. Then $S$ occurs only if the event $M=k$ occurs and also the event $A$ occurs. Since the events $A$ and $M=k$ are independent, we see that \begin{align*} \Pr[S] &= \Pr[A]\cdot\Pr[M=k]\\ \intertext{Of course, $M$ has the binomial distribution, meaning} \Pr[M=k] &= \binom{n-1}{k-1}p^{k-1}(1-p)^{(n-1)-(k-1)}\\ \intertext{Therefore, since $\Pr[A]=p$, we have} \Pr[S] &= p\cdot \binom{n-1}{k-1}p^{k-1}(1-p)^{n-k} \end{align*} \ppart For a given $j$, what is the expected time between the $j^{th}$ and $(j+1)^{st}$ meteor hits? Let $W_j$ be the year the $j^{th}$ meteor hits ($W_0=0$), and let $X_{j}=W_{j+1}-W_{j}$ be the time between the $j^{th}$ and $(j+1)^{st}$ meteor hits. As discussed in tutorial regarding the coupon collector problem, $X_j$ is independent of $W_j$ and has the negative binomial distribution with parameter $p$, so \[ E[X_j] = 1/p. \] \ppart What is the expected life of the space-station? (You will get partial credit for a non-closed form solution, but do not waste time evaluating hairy sums.) By the definitions of the previous section, the time we care about is $W_k=\sum_{j=0}^{k-1}X_j$. It follows by linearity of expectation that \begin{align*} E[W_k] &= E[\sum_{j=0}^{k-1} X_j]\\ &= \sum_{j=0}^{k-1} E[X_i]\\ &= \sum_{j=0}^{k-1} 1/p\\ &= k/p \end{align*} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem Suppose I have an experiment with $n$ possible outcomes, of which the $i^{th}$ happens with probability $p_i$. Suppose I perform the experiment once to establish a ``goal outcome.'' Now I repeat the experiment over and over until the ``goal outcome'' occurs again. Not including the first experiment, what is the expected number of experiments I will perform? (Justify your answer, and do not make any assumptions about the $p_i$'s) Let $G$ be the goal outcome, and let $X$ be the number of experiments that are performed after the first. From the problem definition, we see that \[ \Pr[G=i] = p_i. \] Now suppose that $G=i$. Then we start performing experiments until the outcome $i$ occurs. Since the probability of outcome $i$ is $p_i$, the number of experiments $X$ has the negative binomial distribution with parameter $p_i$. The expected value of this distribution is $1/p_i$. That is, \[ E[X \mid G=i] =1/p_i. \] It follows from the theorem for conditional expectations that \begin{align*} E[X] &= \sum_{i=1}^n E[X \mid G=i] \cdot \Pr[X=i]\\ &= \sum_{i=1}^n \frac1{p_i}\cdot p_i\\ &= \sum_{i=1}^n 1\\ &= n \end{align*} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem Adam and Eve marry and begin having children. Each child is a boy or a girl independently with probability 1/2, and Adam and Eve stop having children once they have two children of the {\bf same} sex. Let $c$ be the expected number of children they have. \bparts \ppart What is the value of $c$? Suppose by symmetry the first child is a boy. Then the second child is a boy with probability $\frac12$, in which case they stop; otherwise, by the pigeonhole principle (two genders, three children), they will stop on their third child. Thus the expected number of children is $2.5$. \ppart Suppose each descendant grows up, marries a non-descendant of Adam and Eve, and follows the same child bearing rules as Adam and Eve. What is the expected {\bf total} number of descendants of Adam and Eve up to and including the $n^{th}$ generation, if Adam and Eve are generation 0, their children generation 1, and so on? Since the number of children born to each couple is independent, we can apply Wald's theorem to the resulting branching process to conclude that the number of children born in generation $n$ is $(2.5)^n)$. Thus the number of descendants up to and including generation $n$ is $\sum_{j=1}^n (2.5)^j$. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{problems} \end{document} \documentstyle[12pt,macpsfig,amssymb]{article} \input{/a/class/6.042/fall94/handouts/macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} \newcommand{\pr}{\problem} \begin{document} \exam{Quiz 1}{October 19, 1991} \begin{closeitemize} \item This quiz ends at 9 {\sc p.m.} It contains ???? problems. You have 120 minutes to earn ????? points. \item This quiz is closed book. You may use one $8\frac{1}{2}''\times 11''$ handwritten crib sheet. \item Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Please do not put part of the answer to one problem on the back of the sheet for another problem. \item Do not spend too much time on any problem. Read them all through first and attack them in the order that allows you to make the most progress. \item Show your work, as partial credit will be given. You will be graded not only on the correctness of your answer, but also on the clarity with which you express it. Be neat. \end{closeitemize} \renewcommand{\arraystretch}{.5} \begin{center} \begin{tabular}{|c|c|c|} \hline & &\hspace*{1in}\\ Problem&Points&Grade\\ & &\\ \hline \hline & &\\ 1 & 10 & \\ & &\\ \hline & &\\ 2 & 10 & \\ & &\\ \hline & &\\ 3 & 10 & \\ & &\\ \hline & &\\ 4 & 10 & \\ & &\\ \hline & &\\ 5 & 10 & \\ & &\\ \hline & &\\ 6 & 10 & \\ & &\\ \hline & &\\ 7 & 10 & \\ & &\\ \hline & &\\ 8 & 10 & \\ & &\\ \hline & &\\ 9 & 10 & \\ & &\\ \hline & &\\ 10 & 10 & \\ & &\\ \hline \hline & &\\ Total & 100 & \\ & &\\ \hline \end{tabular} \end{center} \renewcommand{\arraystretch}{1} \bigskip \bigskip \bigskip \noindent Name:\ \mbox{}\hrulefill\mbox{}\par \newpage \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \pr \points{??} \bparts \ppart Let $p$ be a prime. Prove that if $p\bmod 3 = 1$ then $p\bmod 6 = 1$. \ppart Prove that $3\divides (n^3 + 2n)$ for all $n\in\nats$. \eparts \pr \points{??} \bparts \ppart Use the Euclidean algorithm to find the gcd of 221 and 323. \ppart Find an integer solution to $221x + 323y = 187$. \eparts % DONE BY RANDALL IN RECITATION. % \pr % \points{??} Use induction to prove that for any natural number $n>3$, % $n! > 2^n$. \pr \points{??} Let $G=(V,E)$ be a free tree, and define the relation\\ $R=\{(v_1,v_2)\in V\times V: \mbox{ there is a simple path of even length from $v_1$ to $v_2$} \}$. \bparts \ppart Prove that $R$ is an equivalence relation. \ppart What are the equivalence classes for the graph $G$ below? \eparts \pr \points{??} Let $R_1\subseteq S\times S$ and $R_2\subseteq S\times S$ be two equivalence relations on a set~$S$. \bparts \ppart Is their union, $R_1\cup R_2$, an equivalence relation? Prove your answer. \ppart Is their intersection, $R_1\cap R_2$, an equivalence relation? Prove your answer. \eparts % \pr % \points{??} % Prove that the quotient and the remainder promised by the division % algorithm when $a\in\nats$ is divided by $b\in\nats$ are unique. % % \pr % \points{??} % The media reported that the recent survey % {\em Sex in America$^{\sc pg-13}$} found that in America, men have % kissed(!) an average of six women and women have kissed an average of % two men. Comment from a graph-theoretic point of view. \pr \points{??} Circle {\bf T} or {\bf F} for each of the following statements to indicate whether the statement is true or false, respectively. Also justify your answer, concisely and succinctly. The justification counts for more points than simply the correct {\bf T}/{\bf F} answer. One- or two-sentence explanations or pictures should suffice. \begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}% \setlength{\labelwidth}{\leftmargin}% \addtolength{\labelwidth}{-\labelsep} } \item For all $a,b\in\ints$, every common divisor of $a$ and $b$ can be expressed in the form $ax + by$ for some $x,y\in\ints$. %\vspace*{1.25in} \item For any predicates $P(x)$ and $Q(x)$, we have $\forall x \left( P(x)\land \neg Q(x)\right) \implies \neg\exists x \left( P(x)\implies Q(x)\right)$. %\vspace*{1.25in} \item For any prime $p$, we have $p\divides 1\implies p^2+1 \mbox{ is odd}$. \item For any two different Fibonacci numbers $F_m$ and $F_n$, $\gcd(F_m,F_n)=1$. \item Every undirected graph in which each vertex has degree 3 has an even number of vertices. \item No relation can be both symmetric and antisymmetric. \item $f(x)=x^2-x$ is an injection from $\reals$ to $\reals$. \item $f(x)=x^2-x$ is a surjection from $\reals$ to $\reals$. \item If $C$ is a countable set then $C\times C$ is also countable. \item $n=o(2^{\sqrt{n}})$. \item $2^{\lg ^3n} = \Theta ( n^3)$. \item $\lg (n^3) = \Theta (\lg n)$. \item $n^{3.01} = \omega (n^3 \lg n)$. \item $3^{2n} \sim 9^n$. \item $e^{\ln (n^3)} = \Theta( n^3 )$. \item $1+{1\over 0.9} + \left(1\over 0.9\right)^2 + \left(1\over 0.9\right)^3 \cdots = {1\over 1-0.9} = 10$ \end{list} % \pr % \points{??} % Find an $f(n)$ in closed form such that % $f(n)\sim \sum_{i=1}^{n} i^{-1/2}$. \pr \points{??} % Easy form: % Show that in any set of 10 integers, there are four integers % $a_1,...,a_4$ such that for all $i,j$, $3\divides (a_i-a_j)$. % Hard form: Show that if $n>m(m-1)$, then in any set of $n$ integers there are $m$ integers $a_1,...,a_m$ such that for all $i,j$ we have $m\divides (a_i-a_j)$. \pr \points{??} Let $T_n$ denote the product of all positive even integers less than~$n$. \bparts \ppart Find a closed form expression for $T_n$. (You may leave factorials %and floor functions in your answer.) \ppart Find a function $f(n)$ that does not have sums, products, floors or factorials for which $f(n) \sim T_n$. \eparts \pr \points{??} The cookie monster is searching the supermarket for cookies. He does not know which aisle contains the cookies, and he can tell if an aisle has cookies if he peers down that aisle from the front of the store. Being a large monster (but dumb---he cannot read the signs), in one step he can move from the front of one aisle to the front of either adjacent aisle. He begins at aisle 0 (the center aisle) and follows the following search strategy. He first moves one step to the right to peer down aisle 1, then moves two steps to the left to peer down aisle~$-1$, then moves five step to the right to aisle~$4$ (inspecting the aisles in between as he moves), and in general going back and forth between aisle $m^2$ and aisle $-m^2$, for $m=1,2,3,\ldots$~\ We wonder how efficient this search strategy is---how many steps $s(n)$ the cookie monster takes if the cookies are in aisle~$n$. We are interested in asymptotic efficiency, for today's very large supermarkets: Find a simple expression $f(n)$ that is~$\Theta (s(n))$. \remove{ \pr \points{??} Let $A$ and $C$ be $n\times n$ matrices where $a_{i,j} = 1$ if city $j$ can be reached within a single day of air travel from city $i$, and $c_{i,j} = 1$ if city $j$ can be reached with a single day of car travel from city $i$. Otherwise entries are 0. Show how to compute a matrix $M$ where $m_{i,j} =1$ iff city $j$ can be reached from city $i$ by a single day of air travel followed by a single day of car travel. Also show how to compute $M'$ where $m'_{i,j} =1$ iff city $j$ can be reached from $i$ with 2 days of travel (at most) where each day is all car or all air. } \remove{ \pr \points{??} For each function $f(n)$ along the left side of the table below and each function $g(n)$ across the top, write $O$, $\Omega$, or $\Theta$ in the appropriate space, depending on whether $f(n)=O(g(n))$, $f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$. If there is more than one relation between $f(n)$ and $g(n)$, write only the strongest one. {\em Wrong answers will be penalized, so do not guess unless you are reasonably sure.} The first line is a demo solution. \[ \begin{array}{|c||c|c|c|} \hline & \hspace*{1in} & \hspace*{1in} & \hspace*{1in} \\ & n & n\lg n & n^2\\ & & & \\ \hline \hline & & & \\ 3n\lg n & \Omega & \Theta & O \\ & & & \\ \hline & & & \\ n^{0.99} \lg^2 n& & & \\ & & & \\ \hline & & & \\ 2n^2-5n\lg n& & & \\ & & & \\ \hline & & & \\ \lg(n!)& & & \\ & & & \\ \hline & & & \\ 3^{\lg n}& & & \\ & & & \\ \hline & & & \\ {\displaystyle \sum_{i=1}^n\lg i}& & & \\ & & & \\ \hline \end{array} \] } \end{problems} \end{document} \documentstyle[12pt]{article} \input{/a/class/6.042/spring94/handouts/macros-course} %\newcommand\npage{\vspace{.8in}} \newcommand\npage{\newpage} \setcounter{page}{0} \begin{document} \handout{quiz-2-sols}{Quiz 2 Solutions}{April 22, 1994} %\examinitials{Quiz 2 }{April 20, 1994} \begin{closeitemize} \item This quiz ends at 9 {\sc p.m.} It contains 8 problems. You have 120 minutes to earn 105 points. \item {\bf Initial the top of each page of your quiz. This is worth 5 points.} \item This quiz is closed book. You may use one $8\frac{1}{2}''\times 11''$ handwritten crib sheet. No calculators or electronic playback devices are permitted. \item Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Do not put part of the answer to one problem on the back of the sheet for another problem. \item Do not spend too much time on any problem. Read them all through first and attack them in the order that allows you to make the most progress. \item Show your work, as partial credit will be given. You will be graded not only on the correctness of your answer, but also on the {\bf clarity} with which you express it. {\bf Be neat.} \end{closeitemize} \renewcommand{\arraystretch}{.5} \begin{center} \begin{tabular}{|c|c|c|} \hline & &\hspace*{1in}\\ Problem&Points&Grade\\ & &\\ \hline \hline & &\\ Initials & 5 & \\ & &\\ \hline & &\\ 1 & 10 & \\ & &\\ \hline & &\\ 2 & 10 & \\ & &\\ \hline & &\\ 3 & 14 & \\ & &\\ \hline & &\\ 4 & 16 & \\ & &\\ \hline & &\\ 5 & 16 & \\ & &\\ \hline & &\\ 6 & 10 & \\ & &\\ \hline & &\\ 7 & 10 & \\ & &\\ \hline & &\\ 8 & 14 & \\ & &\\ \hline \hline & &\\ Total & 105 & \\ & &\\ \hline \end{tabular} \end{center} \renewcommand{\arraystretch}{1} \bigskip \bigskip \noindent Name:\ \mbox{}\hrulefill\mbox{}\par \newpage \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\npage%5 %\problem \points{10} How many orderings exist for a standard card %deck of $52$ cards if all the cards of the same suit are adjacent? % %You may leave your answer in terms of factorials and powers. % \npage%6 \problem \points{10} In how many ways can 6 men and 6 women be seated at a round table if men and women must sit in alternate seats? Since the table is round, rotating their positions does not count as a new seating arrangement. You need not simplify your answer---you may leave it in terms of factorials, powers, etc. %You may leave your answer in terms of factorials and powers. \npage%7 \problem \points{10} \begin{problemparts} \problempart What is the number of ways to distribute $n$ distinct toys among $k$ distinct children. There are no constraints on the number of presents a child can receive. \vspace{3in} \problempart How many ways could the toys be distributed if the toys were indistinguishable? \end{problemparts} \npage%8 \problem \points{14} \begin{problemparts} \problempart Use a combinatorial argument to prove that \[ \sum_{k=0}^n {r\choose k} {s \choose n-k} = {r+s\choose n} \] for all natural numbers $r,s,n$. \vspace{2.5in} \problempart Prove the same thing using the binomial theorem and the identity \[(1+x)^r (1+x)^s = (1+x)^{r+s}\quad.\] \end{problemparts} \npage%9 \problem \points{16} \begin{problemparts} \problempart What is the number of 11-combinations of the multiset \mbox{$S = \{\infty\cdot a, \; \infty\cdot b, \; \infty\cdot c, \; \infty\cdot d\}$?} (You need not simplify your answer---% you may leave it in terms of factorials, powers, etc.) \vspace{3in} \problempart Use inclusion-exclusion to determine the number of 11-combinations of the multiset $S = \{\infty\cdot a, \; 4\cdot b, \; 5\cdot c, \; 7\cdot d\}$. (You need not simplify your answer---% you may leave it in terms of factorials, powers, etc.) \end{problemparts} \npage%10 \problem \points{16} Let $a_n$ be the number of $n$-digit numbers composed of the digits $1,2,$ and $3$ such that the number of $1$'s is odd and the number of $2$'s is even. \begin{problemparts} \problempart Find the exponential generating function for the sequence $\langle a_0,a_1,a_2,\ldots\rangle$. \vspace{3.5in} \problempart Find a simple formula for $a_n$. \end{problemparts} \npage%1 \problem \points{10} Suppose you are playing a game that results in either a win or a loss. The outcomes of the games are mutually independent and you win each game with probability $2/3$. Suppose you play 7 times. What is the probability that you win exactly 3 out of the last 4 games? Describe the sample space and show your calculations. \npage%2 \problem \points{10} In a certain village, 20\% of the population has contracted disease $D$. When a person who has the disease is tested for it, he or she tests positive with probability~$9/10$. A person without $D$ tests positive for it with probability~$3/10$. If a villager is chosen uniformly at random and tests positive for $D$, what is the probability that he or she actually has the disease? (This is not a trick question---the probability is not 0 or 1.)\\ Describe the sample space and show your calculations. %\npage%3 %\problem \points{10} %Consider the following version of the Monty Hall game. %You are shown three doors. There is a prize behind %{\em two} of the doors, and a goat behind the other. %As usual, you pick a door. Now however Monty reveals %another door that has a prize behind it. He then offers you %the opportunity either to stick with what's behind the first %door you chose, or to switch and take what's behind the other %unopened door. % %Assume that Monty picks the doors for his prizes (and the %door he opens) at random. %What is the probability of winning if you play the switch %strategy. What is your probability of winning if you don't %switch. Show any necessary calculations. % \npage%4 \problem \points{14} Consider the experiment of tossing three fair coins. The probability for each coin to come up heads is $1/2$, and the results of the three flips are mutually independent. (For this problem you can use either definition of mutual independence that was given in class.) Let $A_1$ be the event that the first coin comes up heads. Let $A_2$ be the event that the first two coins come up the same (that is, they are either both heads or both tails). Let $A_3$ be the event that more coins come up heads than tails. Let $A_4$ be the event that the last coin is tails. \begin{problemparts} \problempart What is the sample space? \vspace{1.8in} \problempart What is the probability of each sample point? \vspace{1.8in} \problempart Calculate $\rm{Prob}[A_4 \mid A_2 \land A_3]$. \vspace{1.8in} \problempart %\points{} Are $A_1$ and $A_2$ independent? Justify your answer. \vspace{2.3in} \problempart Are $A_3$ and $A_4$ independent? Justify your answer. \vspace{2.3in} \problempart %\points{} Find 3 events (from $A_1,\ldots,A_4$) that are mutually independent. Justify your answer. \end{problemparts} % \npage%11 % \problem \points{10} Use generating functions to solve the recurrence % \[ a_n=\left\{ % \begin{array}{ll} % 0&\mbox{if $n=0$} \\ % 3&\mbox{if $n=1$} \\ % a_{n-1} + 2a_{n-2}&\hbox{for $n\ge2$}. \\ % \end{array} \right. \] % For partial credit, just find a simple expression for an ordinary generating % function for the sequence $\langle a_0,a_1,a_2,\ldots\rangle$. % % \npage%12 % \problem \points{10} Use the pigeonhole principle to prove that if % $m$ and $n$ are two positive integers then there exist distinct % natural numbers $i$ and $j$ such that $m^i-m^j$ is divisible by % $n$. % \end{problems} \end{document} \documentstyle[12pt,twoside,prooftree]{article} \input{macros-course} \newcommand{\fortext}[1]{\relax\ifmmode{#1}\else\mbox{$#1$}\fi} \def\z3{\fortext{\integers_{3}}} \def\lte{\fortext{\sqsubseteq}} \newcommand{\lcm}{\mathop{\rm lcm}\nolimits} \newcommand{\subst}[3]{#1[#2 := #3]} \newcommand{\aeval}[2]{{\it val}(#1,#2)} \newcommand{\mean}[1]{\llbracket#1\rrbracket} \newcommand{\provable}{\vdash} \newcommand{\can}[1]{\mbox{canon}(#1)} \begin{document} \handout{quiz1}{Quiz 1}{March 5,1996} This is an OPEN BOOK Quiz: you may refer to books, handouts, or your own course notes. (Calculators not allowed.) You may use in your problem solutions any of the mathematical results given in lectures, recitations, or the course text. There are seven problems to complete within two hours. Good luck! \begin{problems} \problem {\bf [10 pts]} (Induction) Prove that \[ \sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1} \] for integers $n\ge 1$. \problem {\bf [15 pts]} (Induction) % For arithmetic expressions $e,f$ and variable $x$, the {\em substitution}, $\subst{e}{x}{f}$, of $f$ for $x$ in $e$ is defined by induction on $e$: \newcommand{\op}{{\it op}} \begin{eqnarray*}\small \subst{x}{x}{f} &=& f,\\ \subst{c}{x}{f} &=& c \quad \mbox{for any constant or variable, $c$, distinct from } x,\\ \subst{(-e_{0})}{x}{f} &=& -(\subst{e_{0}}{x}{f}),\\ \subst{(e_{0}\ \op\ e_{1})}{x}{f} &=& \subst{e_{0}}{x}{f}\ \op\ \subst{e_{1}}{x}{f}, \quad \mbox{where \op\ $\in\{+,*\}$}\ . \end{eqnarray*} Following Handout 7, we write $\provable e = f$ to indicate that the arithmetic equation $e=f$ is provable in the formal system of the Handout. %%\bparts \ppart Prove that \[ \provable f = g \mbox{ implies } \provable \subst{e}{x}{f} = \subst{e}{x}{g}. \] \iffalse \ppart Prove that \[ \provable e = g \mbox{ implies } \provable \subst{e}{x}{f} = \subst{g}{x}{f}. \] \eparts \fi \problem {\bf [15 pts]} (Number theory) % Give all values of $x\ \mod{143}$ such that \[ 2x = 5 \ \mod{143}\ , \] and briefly indicate your reasoning. \iffalse \problem (GCD's) \bparts \ppart Explicitly describe the set of integer solutions for the equation $40x + 52y = 18$. \ppart Define the {\em least common multiplier}, $\lcm (m,n)$, to be the least integer $k > 0$ such $m | k$ and $n | k$. Prove that for all $m,n > 0$, \[ \lcm (m,n) = \frac{mn}{\gcd(m,n)}. \] \eparts \fi \problem {\bf [10 pts]} (GCD's) % An integer $m$ is a {\em zero-divisor} modulo $n$ iff $m \neq 0 \ \mod n$ and $mk = 0 \ \mod n$ for some $k$ such that $k \neq 0 \ \mod n$. Prove that if $\gcd(m,n) > 1$ and $m \neq 0 \ \mod n$, then $m$ is a zero-divisor modulo $n$. \problem {\bf [15 pts]} (Formal Equational Proofs) % We consider arithmetic equations and inequalities over $\z3$, the integers modulo 3. The definitions for equations are exactly like those for arithmetic over the integers developed in Handout 7, except valuations are specified to be functions from variables to \z3 instead of $\integers$, and the \z3-meaning, $\mean{e}_{3}$, of an arithmetic expression, $e$, is defined with the operations $-$, $+$, $\times$ interpreted over \z3. \iffalse For this interpretation, we obtain a {\em sound} equational proof system, $\provable_{3}$, by using the rules of the equational proof system $\provable$ of Handout 7 along with two additional axioms: \[\small\begin{array}{|rcll|} \hline (e + e) + e &=& 0 & \mbox{($+$-\z3)}\\ (e * e) * e &=& e & \mbox{($*$-\z3)}\\ \hline \end{array}\] \bparts \ppart Exhibit a formal $\provable_3$ proof of the equation $1 + 1 = -1$. \ppart Adding the \z3\ axioms to the proof system $\provable_{\leq}$ of Handout 7 allows a proof of $1 = 0$. But if we further add the rules of the proof system for inequalities, $\provable_{\leq}$, of Handout 7, we can prove $1 = 0$! So, interpreting $\leq$ as the integer order restricted to $\{0,1,2\}$, some of the rules of $\provable_{\leq}$ in Table~\ref{ineq} must not preserve validity for \z3\ inequalities. \fi But if we further interpret $\leq$ as the integer order restricted to $\{0,1,2\}$, some of the rules of $\provable_{\leq}$ in Table~\ref{ineq} do not preserve validity for \z3\ inequalities. Indicate exactly which ones do not, and give simple counterexamples demonstrating where they go wrong. \begin{table}[h] \caption{Inference Rules for Inequalities. \label{ineq}}\small \[\begin{array}{|c|} \hline \\ \prooftree e = f \justifies e \leq f \using \mbox{($\leq$-reflexivity)} \endprooftree \quad \prooftree e \leq f, \quad f \leq e \justifies f = e \using \mbox{($\leq$-antisymmetry)} \endprooftree \quad \prooftree e \leq f, \quad f \leq g \justifies e \leq g \using \mbox{($\leq$-transitivity)} \endprooftree\\ \\ \prooftree e \leq f \justifies e + g \leq f + g \using \mbox{($+$-$\leq$-congruence)} \endprooftree \quad \prooftree e \leq f, \quad 0 \leq g \justifies e * g \leq f * g \using \mbox{($*$-$\leq$-congruence)} \endprooftree \quad \prooftree e \leq f \justifies -f \leq -e \using \mbox{($-$-$\leq$-congruence)} \endprooftree\\ \\ 0 \leq 1 \quad\mbox{($01$-axiom)}\\ \\ \hline \end{array}\] \end{table} \iffalse \ppart For any variable $x$, an {\em $x$-\z3-canonical-form} is an arithmetic expression of the form \[ a_{2}x^{2} + a_{1}x + a_{0} \] (or more formally \Code{((($a_{2}$ * ($x$ * $x$)) + ($a_1$ * $x$)) + $a_0$)}) where each $a_{i}$ is one of the expressions {\tt 0}, {\tt 1}, or {\tt (-1)}. Outline how to find, for every arithmetic expression $e$ containing no variables other than $x$, an $x$-\z3-canonical-form, $\can{e}$, and a formal $\provable_{3}$-proof of the equation $e = \can{e}$. \eparts \fi \problem {\bf [20 pts]} (Equivalence relations) % Let $R,S$ be equivalence relations on some set $A$. Prove that if $R \circ S = S \circ R$, then $R \circ S$ is also an equivalence relation on $A$. \iffalse %%THIS IS THE TWO-PART VERSION OF THE ABOVE PROBLEM \problem (Equivalence relations and $= \mod n$) \bparts \ppart Let $\equiv_n$ be equivalence modulo $n$ on the integers, i.e., $a \equiv_n b$ iff $a = b \mod n$. Prove that for all $m,n > 1$, \begin{eqnarray*} \equiv_n\circ \equiv_m & = & \equiv_m\circ\equiv_n \end{eqnarray*} where $\circ$ denotes composition of binary relations. \ppart Let $R,S$ be equivalence relations on some set $A$. Prove that if $R \circ S = S \circ R$, then $R \circ S$ is also an equivalence relation on $A$. \eparts \fi \problem {\bf [15 pts]} (Schedules for Parallel Tasks) % Let $A$ be the set of nonempty subsets of $\{1,2,\dots,n\}$ for some integer $n>1$. For $a\in A$, let $\max(a)$ be the maximum element in~$a$. We define a partial order \lte\ on $A$ by the rule that \[ a \lte a' \mbox{ iff }\quad \max(a) < \max(a') \mbox{ or } [\max(a) = \max(a') \mbox{ and } a \subseteq a']. \] Give a simple expression in $n$ for the parallel-time, i.e., the length of the shortest schedule, for $(A, \lte)$. (No explanation is necessary. You may include an explanation for partial credit.) \end{problems} \end{document} \documentstyle[12pt,twoside,prooftree]{article} \input{macros-course} \newcommand{\fortext}[1]{\relax\ifmmode{#1}\else\mbox{$#1$}\fi} \def\z3{\fortext{\integers_{3}}} \def\lte{\fortext{\sqsubseteq}} \newcommand{\lcm}{\mathop{\rm lcm}\nolimits} \newcommand{\subst}[3]{#1[#2 := #3]} \newcommand{\aeval}[2]{{\it val}(#1,#2)} \newcommand{\mean}[1]{\llbracket#1\rrbracket} \newcommand{\provable}{\vdash} \newcommand{\can}[1]{\mbox{canon}(#1)} \begin{document} \handout{quiz1}{Quiz 1}{March 5,1996} This is an OPEN BOOK Quiz: you may refer to books, handouts, or your own course notes. (Calculators not allowed.) You may use in your problem solutions any of the mathematical results given in lectures, recitations, or the course text. There are seven problems to complete within two hours. Good luck! \begin{problems} \problem {\bf [10 pts]} (Induction) Prove that \[ \sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1} \] for integers $n\ge 1$. \problem {\bf [15 pts]} (Induction) % For arithmetic expressions $e,f$ and variable $x$, the {\em substitution}, $\subst{e}{x}{f}$, of $f$ for $x$ in $e$ is defined by induction on $e$: \newcommand{\op}{{\it op}} \begin{eqnarray*}\small \subst{x}{x}{f} &=& f,\\ \subst{c}{x}{f} &=& c \quad \mbox{for any constant or variable, $c$, distinct from } x,\\ \subst{(-e_{0})}{x}{f} &=& -(\subst{e_{0}}{x}{f}),\\ \subst{(e_{0}\ \op\ e_{1})}{x}{f} &=& \subst{e_{0}}{x}{f}\ \op\ \subst{e_{1}}{x}{f}, \quad \mbox{where \op\ $\in\{+,*\}$}\ . \end{eqnarray*} Following Handout 7, we write $\provable e = f$ to indicate that the arithmetic equation $e=f$ is provable in the formal system of the Handout. %%\bparts \ppart Prove that \[ \provable f = g \mbox{ implies } \provable \subst{e}{x}{f} = \subst{e}{x}{g}. \] \iffalse \ppart Prove that \[ \provable e = g \mbox{ implies } \provable \subst{e}{x}{f} = \subst{g}{x}{f}. \] \eparts \fi \problem {\bf [15 pts]} (Number theory) % Give all values of $x\ \mod{143}$ such that \[ 2x = 5 \ \mod{143}\ , \] and briefly indicate your reasoning. \iffalse \problem (GCD's) \bparts \ppart Explicitly describe the set of integer solutions for the equation $40x + 52y = 18$. \ppart Define the {\em least common multiplier}, $\lcm (m,n)$, to be the least integer $k > 0$ such $m | k$ and $n | k$. Prove that for all $m,n > 0$, \[ \lcm (m,n) = \frac{mn}{\gcd(m,n)}. \] \eparts \fi \problem {\bf [10 pts]} (GCD's) % An integer $m$ is a {\em zero-divisor} modulo $n$ iff $m \neq 0 \ \mod n$ and $mk = 0 \ \mod n$ for some $k$ such that $k \neq 0 \ \mod n$. Prove that if $\gcd(m,n) > 1$ and $m \neq 0 \ \mod n$, then $m$ is a zero-divisor modulo $n$. \problem {\bf [15 pts]} (Formal Equational Proofs) % We consider arithmetic equations and inequalities over $\z3$, the integers modulo 3. The definitions for equations are exactly like those for arithmetic over the integers developed in Handout 7, except valuations are specified to be functions from variables to \z3 instead of $\integers$, and the \z3-meaning, $\mean{e}_{3}$, of an arithmetic expression, $e$, is defined with the operations $-$, $+$, $\times$ interpreted over \z3. \iffalse For this interpretation, we obtain a {\em sound} equational proof system, $\provable_{3}$, by using the rules of the equational proof system $\provable$ of Handout 7 along with two additional axioms: \[\small\begin{array}{|rcll|} \hline (e + e) + e &=& 0 & \mbox{($+$-\z3)}\\ (e * e) * e &=& e & \mbox{($*$-\z3)}\\ \hline \end{array}\] \bparts \ppart Exhibit a formal $\provable_3$ proof of the equation $1 + 1 = -1$. \ppart Adding the \z3\ axioms to the proof system $\provable_{\leq}$ of Handout 7 allows a proof of $1 = 0$. But if we further add the rules of the proof system for inequalities, $\provable_{\leq}$, of Handout 7, we can prove $1 = 0$! So, interpreting $\leq$ as the integer order restricted to $\{0,1,2\}$, some of the rules of $\provable_{\leq}$ in Table~\ref{ineq} must not preserve validity for \z3\ inequalities. \fi But if we further interpret $\leq$ as the integer order restricted to $\{0,1,2\}$, some of the rules of $\provable_{\leq}$ in Table~\ref{ineq} do not preserve validity for \z3\ inequalities. Indicate exactly which ones do not, and give simple counterexamples demonstrating where they go wrong. \begin{table}[h] \caption{Inference Rules for Inequalities. \label{ineq}}\small \[\begin{array}{|c|} \hline \\ \prooftree e = f \justifies e \leq f \using \mbox{($\leq$-reflexivity)} \endprooftree \quad \prooftree e \leq f, \quad f \leq e \justifies f = e \using \mbox{($\leq$-antisymmetry)} \endprooftree \quad \prooftree e \leq f, \quad f \leq g \justifies e \leq g \using \mbox{($\leq$-transitivity)} \endprooftree\\ \\ \prooftree e \leq f \justifies e + g \leq f + g \using \mbox{($+$-$\leq$-congruence)} \endprooftree \quad \prooftree e \leq f, \quad 0 \leq g \justifies e * g \leq f * g \using \mbox{($*$-$\leq$-congruence)} \endprooftree \quad \prooftree e \leq f \justifies -f \leq -e \using \mbox{($-$-$\leq$-congruence)} \endprooftree\\ \\ 0 \leq 1 \quad\mbox{($01$-axiom)}\\ \\ \hline \end{array}\] \end{table} \iffalse \ppart For any variable $x$, an {\em $x$-\z3-canonical-form} is an arithmetic expression of the form \[ a_{2}x^{2} + a_{1}x + a_{0} \] (or more formally \Code{((($a_{2}$ * ($x$ * $x$)) + ($a_1$ * $x$)) + $a_0$)}) where each $a_{i}$ is one of the expressions {\tt 0}, {\tt 1}, or {\tt (-1)}. Outline how to find, for every arithmetic expression $e$ containing no variables other than $x$, an $x$-\z3-canonical-form, $\can{e}$, and a formal $\provable_{3}$-proof of the equation $e = \can{e}$. \eparts \fi \problem {\bf [20 pts]} (Equivalence relations) % Let $R,S$ be equivalence relations on some set $A$. Prove that if $R \circ S = S \circ R$, then $R \circ S$ is also an equivalence relation on $A$. \iffalse %%THIS IS THE TWO-PART VERSION OF THE ABOVE PROBLEM \problem (Equivalence relations and $= \mod n$) \bparts \ppart Let $\equiv_n$ be equivalence modulo $n$ on the integers, i.e., $a \equiv_n b$ iff $a = b \mod n$. Prove that for all $m,n > 1$, \begin{eqnarray*} \equiv_n\circ \equiv_m & = & \equiv_m\circ\equiv_n \end{eqnarray*} where $\circ$ denotes composition of binary relations. \ppart Let $R,S$ be equivalence relations on some set $A$. Prove that if $R \circ S = S \circ R$, then $R \circ S$ is also an equivalence relation on $A$. \eparts \fi \problem {\bf [15 pts]} (Schedules for Parallel Tasks) % Let $A$ be the set of nonempty subsets of $\{1,2,\dots,n\}$ for some integer $n>1$. For $a\in A$, let $\max(a)$ be the maximum element in~$a$. We define a partial order \lte\ on $A$ by the rule that \[ a \lte a' \mbox{ iff }\quad \max(a) < \max(a') \mbox{ or } [\max(a) = \max(a') \mbox{ and } a \subseteq a']. \] Give a simple expression in $n$ for the parallel-time, i.e., the length of the shortest schedule, for $(A, \lte)$. (No explanation is necessary. You may include an explanation for partial credit.) \end{problems} \end{document} \documentstyle[12pt,macpsfig,psfig,amssymb]{article} \input{macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} %\newcommand{\pr}{\problem} \begin{document} \pquiz{1}{October 3, 1996} \center{(Quiz \#1 and Solutions, Fall 1995)} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %1 \problem \bparts \ppart Use Euclid's algorithm to find the $gcd$ of $241$ and $178$. \bigskip $ \begin{array}{lccrr} & 241 & 178 & 65 & -88 \\ 1 & 178 & 63 & -25 & 65 \\ 2 & 63 & 52 & 19 & -23 \\ 1 & 52 & 11 & -4 & 19 \\ 4 & 11 & 8 & 3 & -4 \\ 1 & 8 & 3 & -1 & 3 \\ 2 & 3 & 2 & 1 & -1 \\ 1 & 2 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 & 0 \end{array}$ Hence, $gcd(241,178) = 1$. \ppart Find an integer solution to $241x + 178y = 10.$ \bigskip From part a) we have \[ gcd(241,178) = 65\cdot 241 - 88\cdot 178 = 1.\] Multiplying by $10$ we get \[ 650\cdot 241 - 880\cdot 178 = 10.\] Hence, one solution is $x = 650$ and $y = -880.$ \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %2 \problem Let $S$ be a set of $n$ positive integers. For any subset $A \subset S$ let $\Sigma(A)$ denote the sum of the elements in $A$. You are given that $\Sigma(S) \leq 2^n - 2.$ \bparts \ppart Prove that there exist two distinct non-empty sets $A$ and $B$ such that $\Sigma(A) = \Sigma(B)$. \bigskip \begin{proof} Consider ${\cal C} = {\cal P}(S) - \{S,\phi\}$. This is the collection of all nonempty subsets of $S$, excluding $S$. $|{\cal C}| = 2^n -2$. For any $A \in {\cal C}$ it is the case that $1 \leq \Sigma(A) \leq 2^n - 3$. It is clear that $1 \leq \Sigma(A)$ since $S$ is a set of positive integers and $A$ is a nonempty subset of it. It is also clear that $\Sigma(A) \leq 2^n - 3$, since $A$ is a proper subset of $S$ and hence $\Sigma(A) < \Sigma(A) \leq 2^n - 2$. Thus we have $2^n-2$ elements $A$ in ${\cal C}$ such that $1 \leq \Sigma(A) \leq 2^n - 3$. By the pigeonhole principle, we have that there exist two sets $A, B \in {\cal C}$ such that $\Sigma(A) = \Sigma(B)$. By construction we have that $A$ and $B$ are distinct non-empty subsets of $S$. \end{proof} \ppart Prove that there exist two distinct non-empty sets $A$ and $B$ such that $\Sigma(A) = \Sigma(B)$ and $A \cap B = \phi.$ \bigskip \begin{proof} Let $A'$ and $B'$ be the two sets from part a). It is the case that $A' \not\subset B'$ and $B' \not\subset A'$ because for any two sets $P,Q \subset S$ it is the case that $P \subset Q \Rightarrow \Sigma(P) < \Sigma(Q)$. Now consider, $A = A' - A' \cap B'$ and $B = B' - A' \cap B'$. It is clear that $\Sigma(A) = \Sigma(B)$ and $A \cap B = \phi.$ Hence we are done. \end{proof} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %3 \problem \points{20} Let $(a,b) \sim (c,d)$ if $a+d = b+c$. \bparts \ppart \points{10} Prove that $\sim$ is an equivalence relation on $\integers \times \integers$. \bigskip \begin{itemize} \item {\em Reflexivity} $(a,b) \sim (a,b)$ since $a + b = b + a$. \item {\em Symmetry} $(a,b) \sim (c,d) \Rightarrow (c,d) \sim (a,b)$ since $a + d = b + c \Rightarrow c + b = d + a$. \item {\em Transitivity} Assume $(a,b) \sim (c,d)$, i.e. $ a + d = b + c$. And, $(c,d) \sim (e,f)$, i.e. $c + f = d + e$. Adding we get $a + d + c + f = b + c + d + e$ or $a + f = b + e$, i.e. $(a,b) \sim (e,f)$. Hence $(a,b) \sim (c,d) \wedge (c,d) \sim (e,f) \Rightarrow (a,b) \sim (e,f)$. \end{itemize} Since $\sim$ is reflexive, symmetric and transitive it is an equivalence relation. \ppart Partition the set $\{0,1,2\} \times \{0,1,2\}$ into the distinct equivalence classes under $\sim$. \bigskip We can rewrite $(a,b) \sim (c,d)$ if $a+d = b+c$ as $(a,b) \sim (c,d)$ if $a-b = c -d$. This shows that with any equivalence class ${\cal C}$ we can associate a {\em difference} $d$ such that $(a,b) \in {\cal C} \Rightarrow a - b = d$. This gives us an easy way to list the equivalence classes of $\{0,1,2\} \times \{0,1,2\}$. \begin{itemize} \item $d = -2$ : $\{(0,2)\}$. \item $d= -1$ : $\{(0,1),(1,2)\}$. \item $d= 0$ : $\{(0,0),(1,1),(2,2)\}$. \item $d= 1$ : $\{(1,0),(2,1)\}$. \item $d= 2$ : $\{(2,0)\}$. \end{itemize} \ppart How many distinct equivalence classes under $\sim$ are there on the set $\{0,1,\ldots, n\} \times \{0,1,\ldots, n\}$. You do not need to prove your answer. \bigskip $2n+1$ since the difference can be any value in $\{-n,\ldots, n\}$. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %4 \problem Prove by induction that \[ {\displaystyle \sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2}.\] \bigskip Let $P(n)$ be ``${\displaystyle \sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2}.$''\\ {\em Base case.} $P(1)$ is true since ${\displaystyle \sum_{i=1}^1 i^3 = 1 = \left(\sum_{i=1}^1 i\right)^2}$. \\ {\em Inductive step.} Assume $P(n)$ is true. Then \[ {\displaystyle \sum_{i=1}^n i^3 = \left(\sum_{i=1}^n i\right)^2}.\] Adding $(n+1)^3$ to both sides we get, $ \begin{array}{lccr} {\displaystyle \sum_{i=1}^{n+1} i^3} & = &\left({\displaystyle \sum_{i=1}^n i}\right)^2 + (n+1)^3 & \\ & = & (n(n+1)/2)^2 + (n+1)^3 & \mbox{since ${\displaystyle \sum_{i=1}^n i} = n(n+1)/2$} \\ & = &(n+1)^2/4 \times (n^2 + 4(n+1)) & \\ & = &((n+1)(n+2)/2)^2 & \\ & = & \left({\displaystyle \sum_{i=1}^{n+1} i}\right)^2 \end{array}$ Hence, $P(n+1)$ is true. Thus $P(n)$ is true for all $n$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %5 \problem $n$ teams play a tournament. Every team plays every other team exactly once and all games end in a win/loss. It is possible that weaker teams can beat stronger teams. \bparts \ppart Any tournament can be viewed as a relation on the set of teams, with $(A,B)$ in the relation iff $A$ beats $B$. Is this relation a partial order for all tournaments? If yes, prove it. If not list all partial order properties that can fail. \bigskip Reflexivity fails since $(A,A)$ does not belong to the relation of the tournament. Transitivity can fail since it could be in a tournament that $A$ beats $B$ who beats $C$ who in turn beats $A$, i.e. $(A,B)$ and $(B,C)$ could be in the relation of the tournament without there also being $(A,C)$. (Note that anti-symmetry holds vacuously, since we never have both $(A,B)$ and $(B,A)$ in the relation.) \ppart Show (by induction) that in any tournament there exists a two-step champion, i.e. there exists a team $A$ such that for every other team $B$ \\ \[ \mbox{it is the case that } \left\{ \begin{array}{l} \mbox{ $A$ has beaten $B$, or} \\ \mbox{ there exists $C$ such that $A$ has beaten $C$ who has beaten $B$.} \end{array} \right. \] \bigskip \begin{proof} Let $P(n)$ be ``in any tournament with $n$ teams there exists a two-step champion.'' \\ {\em Base case.} $P(2)$ is true since in a tournament with only two teams the winner is a two-step champion. \\ {\em Inductive step.} Assume $P(n)$ is true. Consider a tournament with $n+1$ teams numbered $1, 2, \ldots, n+1$. Then the games between teams $1, 2, \ldots, n$ forms a subtournament and hence, by the inductive hypothesis, it must be the case that this subtournament possesses a two-step champion. Let this two-step champion be the team numbered $1$ without loss of generality. Now, if $n+1$ loses to $1$ or any of the teams that lost to $1$ then it is clear that $1$ is a two-step champion for the whole tournament. Otherwise, it is the case that $n+1$ beat $1$ and all the teams that lost to $1$ which makes $n+1$ the two-step champion. In either case the tournament possesses a two-step champion. Thus $P(n+1)$ is true. Hence $P(n)$ is true for all $n$. \end{proof} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %6 \problem \bparts \ppart Show that the set of real numbers $\in (0,1)$ that have only $3$s and $7$s in their decimal representation is uncountable. \bigskip \begin{proof} Suppose the set ${\cal C}$ of real numbers $\in (0,1)$ that have only $3$s and $7$s in their decimal representation is countable. Then there exists a bijection $f: \naturals \rightarrow {\cal C}$. Represent this by a matrix $M$ where $M_{ij} = 3$ if the $j$th digit of $f(i)$ (after the decimal point) is $3$, and $M_{ij} = 7$ otherwise. Now create a new number $T$ by considering the diagonal elements $M_{ii}$ of the matrix. $i$th digit of $T = 3$ if $M_{ii} = 7$, otherwise $i$th digit of $T = 7$. This is a valid element of ${\cal C}$ and $f^{-1}(T)$ must exist. But observe that if the $f^{-1}(T)$th digit of $f^{-1}(T)$ is $3$ then the $f^{-1}(T)$th digit of $f^{-1}(T)$ must be $7$ and vice-versa. Thus, either way, we have a contradiction. Hence ${\cal C}$ cannot be countable. \end{proof} \ppart Prove that the cross product of two countable sets is countable. \bigskip \begin{proof} Let the two sets be $A = \{a_1,a_2,\ldots\}$ and $B = \{b_1, b_2,\ldots\}$. We can list the elements of the sets in this fashion because they are countable and hence have a bijection with the naturals. We list the cross product, using the idea of dove-tailing shown in class, to get the listing $\{ (a_1,b_1),(a_1,b_2),(a_2,b_1),(a_1,b_3),(a_2,b_2), (a_3,b_1), \ldots \}$. It is easy to see that $(a_i,b_j)$ will occur before position $(i+j)^2$ in our listing. Since we have been able to give a valid listing $A \times B$ is countable. \end{proof} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \iffalse %7 \pr \points{20} The following poset shows the ``prerequisite'' dependencies among the computer science courses required for an M.Eng degree at MIT. (It is not factually accurate.) The dependencies go upwards. \begin{figure}[htbp] \centerline{\psfig{figure=course6.ps,height=2in}} \caption{A poset of course 6 prerequisite dependencies} \label{fig:inter} \end{figure} \bparts \ppart Given that there is no limit to the number of courses an MIT student can take in a term, what is the minimum number of terms needed for an MIT student to to get a course 6 M.Eng degree. \ppart Harvard students are allowed to enroll for at most two courses a term at MIT. What is the minimum number of terms a Harvard student will take to get a course 6 M.Eng degree. \eparts \fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{problems} \end{document} \documentstyle[12pt,twoside]{article} \input{macros-course} \begin{document} \quizinfo{1}{October 3, 1996} \noindent \begin{center} \large{\underline{The quiz will be {\bf HARD}!}} \vspace*{.2in} \underline{When:} {\large Wednesday, October 16, 7:00 to 9:00 PM}\\ \underline{Students with conflicts only}: 9:00 to 11:00 PM\\ \vspace*{.2in} (NOTE: Students who take the quiz 7:00 to 9:00 PM, {\bf MUST} stay until 9:00 PM; students who take it 9:00 to 11:00 PM, {\bf MUST} enter the exam room by 9:00 PM.) \vspace*{.2in} \underline{Where:} {\large 54-100} \vspace*{.2in} \underline{Crib Sheet:} {\large The quiz is not open-book, but you are allowed to bring one 2-sided sheet to the exam. You may have whatever information you like on it but it must be handwritten and must not be xeroxed.} \vspace*{.2in} \underline{Syllabus:} {\large Everything done until and including the recitation on October 11.} \vspace*{.2in} \underline{Make-up Exam:} {\large If you have a conflict come see us NOW.} \vspace*{.2in} \underline{Special office hours:} {\large There will be special office hours during quiz-week as follows}: \end{center} \( \begin{array}{llll} Mojdeh: & Tuesday, & October 15, & 9-11\\ Alex: & Tuesday, & October 15, & 4-6\\ Dimitri: & Tuesday, & October 15, & 5-7\\ Gunnar: & Wednesday, & October 16, & 2-4\\ Yong~Yeow: & Wednesday, & October 16, & 4-6 \end{array} \) \vspace*{.3in} \end{document} \documentstyle[12pt,twoside]{article} \input{macros-course} \begin{document} \quizinfo{2}{November 5, 1996} \noindent \begin{center} \vspace*{.2in} \underline{When:} {\large Wednesday, November 13, 7:00 to 9:00 PM}\\ %\underline{Students with conflicts only} (these are the students who %have already contacted Mojdeh. They will soon receive an email from %Mojdeh confirming this): 9:00 to 11:00 PM\\ %\vspace*{.2in} %(NOTE: Students who take the quiz 7:00 to 9:00 PM, {\bf MUST} stay %until 9:00 PM; students who take it 9:00 to 11:00 PM, {\bf MUST} enter %the exam room by 9:00 PM.) \vspace*{.2in} \underline{Where:} {\large 54-100} \vspace*{.2in} \underline{Crib Sheet:} {\large The quiz is not open-book, but you are allowed to bring two 2-sided sheets to the exam. You may have whatever information you like on it but it must be handwritten and must not be xeroxed.} \vspace*{.2in} \underline{Syllabus:} {\large Everything done until and including the recitation on November 8.} \vspace*{.2in} %\underline{Make-up Exam:} {\large If you have a conflict come see us NOW.} %\vspace*{.2in} \underline{Special office hours:} {\large There will be special office hours during quiz-week as follows}: \end{center} \( \begin{array}{lllll} Mojdeh: & Tuesday, & November~12, & 9-11 & NE43-369\\ Alex: & Friday, & November~8, & 4-6 & NE43-308\\ Dimitri: & Tuesday, & November~12, & 6-8 & 10-178\\ Gunnar: & Wednesday, & November~13, & 4-6 & NE43-370\\ Yong~Yeow: & Wednesday, & November~13, & 9-11 & NE43-369\\ \end{array} \) \vspace*{.3in} \end{document} \documentstyle[12pt,macpsfig,psfig,amssymb]{article} \input{macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} %\newcommand{\pr}{\problem} \begin{document} \pquiz{2}{October 31, 1996} \center{(Quiz \#2 and Solutions, Fall 1995)} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %1 \problem \bparts \ppart Give tight ($\Theta$) bounds for \[{\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}}.\] \bigskip \begin{eqnarray*} {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\ {\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\ 2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\ {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 1}{\sqrt{n}}} \\ 2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\ \end{eqnarray*} That is \[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\] \ppart Express the following in closed form \[ {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q}.\] (Note that the lower indices are not constants.) \bigskip \begin{eqnarray*} {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q} & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{q=p}^{\infty} y^{q-p}} & \\ & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{r=0}^{\infty} y^r} & \\ & = {\displaystyle \left( \sum_{p=1}^{\infty} x^py^p \right) \left( \sum_{r=0}^{\infty} y^r \right)} & \\ & = \left( \frac{xy}{1-xy}\right)\left( \frac{1}{1-y}\right). \end{eqnarray*} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %2 \problem I have $n$ one-dollar bills that I wish to donate to $m$ charities. \bparts \ppart In how many ways can I do this if I don't care how much each charity gets? \bigskip Simply insert $m-1$ bars into a string of $n$ one-dollar bills. Then the $i$-th charity gets the money between bars $i-1$ and $i$. This gives you ${n+m-1 \choose m-1 } $ ways to distribute the money. \ppart In how many ways can I do this so that each charity gets at least \$ $10$? \bigskip First give 10 dollars to each charity, then distribute the remaining $n-10m$ dollars as in part a. This gives you ${n+m-1-10m \choose m-1}= {n-9m-1 \choose m-1}$ ways as long as $n\geq 10m$. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %3 \problem In how many ways can $5$ indistinguishable covered wagons, $4$ indistinguishable uncovered wagons and $1$ horse be arranged in a circle? \bigskip This problem is just a permutation of a multiset, except that we need to account for rotations of a circle being the same. This can be thought of either as fixing one object, say the horse, and arranging the wagons around it (${9\choose 5}$ ways), or counting the permutations and dividing by $10$ to avoid overcounting the rotations ($\frac{1}{10}\frac{10!}{5!4!1!}$). Either way the answer is 126. The most common mistake was to forget about overcounting the rotations. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %4 \problem How many $6$-digit decimal numbers are there that do not contain ``$123$'' or ``$456$'' as a subsequence? (for purposes of this problem numbers may have leading $0$'s) \bigskip Let \begin{itemize} \item $A$ be the set of all six-digit strings, using the digits $\{0, 1, \ldots, 9\}$. \item $B$ be the set of six-digit strings that contain the subsequence $123$. \item $C$ be the set of all six-digit strings that contain the subsequence $456$. \item $D$ be the set of all six-digit strings that do not contain $123$ or $456$. \end{itemize} We're interested in figuring out $| D |$. Since $$D = A - (B \cup C),$$ and $B \cup C \subseteq A$, we can use the inclusion-exclusion formula: $$| D | = | A | - |B \cup C| = | A | - | B | - | C | + | B \cap C |.$$ First, $|A| = 10^6$, since we can put any of ten digits in each of six places. Now, a string can contain $123$ in any of four positions; once this position is chosen, we have $1000$ choices for the remaining positions. However, this approach counts the string $123123$ twice, so the total size of $B$ is $$| B | = 4(1000) - 1 = 3999.$$ By the same reasoning, we get $$| C | = 3999.$$ Finally, there are only two strings in $B \cap C$, namely $123456$ and $456123$. Thus, $$| B \cap C | = 2.$$ Plugging this into our formula, we get $$| D | = 10^6 - 3999 - 3999 + 2 = 992004.$$ {\em (Common Mistakes: A lot of people forgot about the double-counting of $123123$ and $456456$, and so had $|B| = |C| = 4000$. Some people also argued that since $123$ can appear in one of only four places in the string, $|B| = 4$.)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %5 \problem Consider the following nuclear reaction. There is one particle of type $1$ at time instant $1$. Each particle of type $i$ existing at time $t$ undergoes fission to produce one particle of type $i+1$ and one of type $i+2$ at time instant $t+1$. \bparts \ppart Write and justify a recurrence for $f(i,t)$, the number of particles of type $i$ at time $t$. (Make sure to include the base cases for your recurrence.) \bigskip Particles of types $i-2$ and $i-1$ at time $t-1$ give rise to particles of type $i$ at time $t$ and this is the only way that particles of type $i$ are formed at time $t$. Hence we get the recurrence \[ f(i,t) = f(i-1,t-1) + f(i-2,t-1), t > 1. \] The base case is \begin{itemize} \item $f(1,1) = 1$. \item $f(i,1) = 0, -\infty \leq i \leq \infty, i \not= 1$. \end{itemize} \ppart Prove by induction that $f(i,t) = {t-1\choose i-t}$. (You do not need to reprove identities that were proven in class.) \bigskip (Note: Let $a$ be any nonnegative integer and $b$ be any integer. In what follows, we use the definition that ${a\choose b} = \frac{a!}{b!(a-b)!}$ when $a\geq b \geq 0$ and otherwise ${a\choose b} = 0$ when . Pascal's identity holds for this definition.) The proof is by induction on $t$. Let $P(t)$ be \[f(i,t) = {t-1\choose i-t}, \forall i.\] Base Case. $P(1)$ is true since \begin{itemize} \item $f(1,1) = {0\choose 0} = 1$. \item $f(i,1) = {0\choose i-1} = 0, -\infty \leq i \leq \infty, i \not= 1$. \end{itemize} Inductive step. Assume $P(t)$ is true. Consider $P(t+1)$. \begin{eqnarray*} f(i,t+1) & = f(i-1,t) + f(i-2,t) & \mbox{ by the recurrence from part a)}\\ & = {t-1\choose i-1-t} + {t-1\choose i-2-t} & \mbox{ by inductive hypothesis} \\ & = {t\choose i-1-t} & \mbox{ by Pascal's identity} \end{eqnarray*} Hence $P(t+1)$ is true. Thus $P(t)$ is true for all $t$ and we are done. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %6 \problem \bparts \ppart Give tight ($\Theta$) bounds for $T(n)$. Assume that $T(n)$ is constant for $n \leq 10$. \[T(n) = 4T(n/2) + 6n.\] \bigskip \begin{eqnarray*} T(n) & = 4T(n/2) + 6n & \\ & = 4^2T(n/2^2) + 6(n + n/2) & \\ & = \ldots & \\ & = 4^iT(n/2^i) + 6(n + n/2 + \ldots + n/2^{i-1}) & \\ & = \ldots & \\ & = 4^{\log_2 n}T(1) + 6(n + n/2 + \ldots + n/2^{\log_2 n \ -1}) & \\ & = n^2T(1) + O(n) & \\ & = \Theta(n^2) \end{eqnarray*} \ppart \points{10} Rank the following functions by order of growth; that is find an arrangement $g_1 = \alpha(g_2) = \alpha(g_3) = \ldots = \alpha(g_6)$ and state whether $\alpha$ is $o$ or $\Theta$ for each step. \begin{itemize} \item $n(\log_2 n)^5$ \item $n^3$ \item $n!$ \item $(n!)^2$ \item $n^n$ \item $3\cdot 8^{\log_2 n} + 4^{\log_2 n}$ \end{itemize} \bigskip \[ n(\log_2 n)^5 = o(n^3) = \Theta(3\cdot 8^{\log_2 n} + 4^{\log_2 n}) = o(n!) = o(n^n) = o((n!)^2). \] \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %7 \problem \bparts \ppart Let $p_k$ be the number of ways to make change of $k$ cents with indistinguishable pennies ($1$-cent coins). Give an ordinary generating function for $p_k$. \bigskip \[\frac{1}{1-x}.\] \ppart Let $n_k$ be the number of ways to make change of $k$ cents with indistinguishable nickels ($5$-cent coins). Give an ordinary generating function for $n_k$. \bigskip \[\frac{1}{1-x^5}.\] \ppart Let $s_k$ be the number of ways to make change of $k$ cents with indistinguishable pennies or nickels. Give an ordinary generating function for $s_k$. \bigskip \[\left( \frac{1}{1-x}\right) \left( \frac{1}{1-x^5} \right). \] \ppart Give an ordinary generating function for the number of ways to make change of $k$ cents with at least $3$ nickels and an odd number of pennies. (this part may be a little hard so don't knock yourself out trying to solve it.) \bigskip \[\left( \frac{x^{15}}{1-x^5}\right) \left( \frac{x}{1-x^2} \right). \] \eparts \end{problems} \end{document} \documentstyle[12pt,macpsfig,psfig,amssymb]{article} \input{macros-course} %\addtolength{\topmargin}{-.2in} %\setlength{\textheight}{9in} \setcounter{page}{0} \begin{document} \examinitials{Review for Quiz 2}{April 15, 1997} \long\def\comment#1{} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %6 \problem Prove that among any set of 150 natural numbers, there must be three numbers, $a$, $b$, and $c$, such that all the pairwise differences, $a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70. \comment{ \bigskip \begin{proof} Use Pigeonhole. \\ {\bf Pigeons} The 150 numbers. \\ {\bf Holes} The natural numbers mod $70$. \\ There is some hole with $ \ceil{\frac{150}{70}} = 3$ pigeons, that is, three numbers $a,b,c$ that are equivalent modulo $70$. Then their differences are equivalent to $0$ modulo $70$, therefore they are divisible by $70$. \end{proof} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %7 \problem For each of the following sets, decide whether the set is countable or uncountable and prove your answer. (If an answer to one part of the question follows from an answer you have already given to another part, then you need only show that is follows -- you don't need to prove the second part from scratch.) \\ \bparts \ppart The set $E$ of all the even natural numbers. \\ \comment{ \bigskip This set is countable. The function $f(n) = 2n$ is a bijection from $\naturals$ to $E$. \bigskip } \ppart The set of all subsets of $E$. \\ \comment{ \bigskip This set is uncountable. The power set of any set has bigger cardinality than the original set. \\ \bigskip} \ppart The set of all finite subsets of $E$. \\ \comment{ \bigskip \ Let $S_{i} =$ { The set of all subsets of E with $i$ elements. } \\ Each of the $S_{i}$ is countable and the set under question is the countable union of all the $S_{i}$, therefore it is countable. \\ \bigskip } \ppart The set of all even-size finite subsets of $E$. \\ \comment{ \bigskip This set is countable, being a subset of the set in part (c). \\ } \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %8 \problem The CS department has just completed a revamping of its curriculum. The following 10 courses are now required: 6.001, 6.002, 6.003, \dots , 6.009, and 6.042.\\ In addition, for every $i,j$, 6.00$i$ is a prerequisite of 6.00$j$ or 6.0j, if $i < j$ and $gcd(i,j) > 1$. \\ \vspace{.01in} \bparts \ppart Write down all the elements of the {\em prerequisite} relation. \\ \comment{ \bigskip {\em prerequisite} $=$ \{ (6.002,6.004) , (6.002,6.006) , (6.002,6.008) , (6.002,6.0042) \\ (6.003,6.006) , (6.003,6.009) , (6.003,6.042) , (6.004,6.006) \\ (6.004,6.008) , (6.004,6.042) , (6.006,6.008) , (6.006,6.042) \\ (6.007,6.042) , (6.008,6.042) , (6.009,6.042) , (6.006,6.009) \} \\ \bigskip } \ppart State whether this relation is reflexive, symmetric, transitive, antisymmetric. Is it an equivalence relation? \\ \comment{ \bigskip The relation is antisymmetric, but nothing else. \\ \vspace{3.5in} \begin{center} Problem continued on the next page. \end{center} } \ppart Now consider the {\em taken before} relation which is defined to be the reflexive and transitive closure of the {\em prerequisite} relation. Draw the Hasse Diagram for the {\em taken before} relation. \\ %\vspace{2.5in} \ppart The new regulations place no limit on how many courses a student can take in one term. What is the minimum number of terms required to complete all the required courses? Why? \\ \comment{ \bigskip The minimum number of terms is $5$, which is the length of the critical path in the above Hasse diagram. \\ \bigskip} \ppart Write down a maximum-size antichain in the partial order. What is the meaning of an antichain in terms of a student's schedule?\\ \comment{ \bigskip 6.001, 6.002, 6.003, 6.005, 6.007. \\ An antichain is a list of subjects that a student can take at the same term. \\ } \eparts \problem An {\em independent set} in a graph is a subset $S$ of the vertices such that no edge connects two vertices in $S$. Consider the following algorithm on a graph with vertices $v_1,\ldots,v_n$: \begin{tabbing} else \= else \= else \= else\kill initially no vertex is marked\\ {\bf for} $i=1$ to $n$\\ \> {\bf if} no neighbor of $v_i$ is marked {\bf then}\\ \> \> mark $v_i$\\ \end{tabbing} \begin{problemparts} \ppart Prove that when this algorithm terminates, the set of marked vertices is an independent set. \ppart {\bf (Optional)} Prove that the set of marked vertices is a {\em maximal} (under containment) independent set, in that adding any other vertex will make it not-independent. \end{problemparts} \problem We know that trees are bipartite because they contain no odd cycles. Give a direct proof that trees are bipartite by induction on the number of tree vertices. \problem Sums. \bparts \ppart Give tight ($\Theta$) bounds for \[{\displaystyle \sum_{i=1}^n i^{1/3}}.\] \comment{ \bigskip \begin{eqnarray*} {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\ {\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\ 2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\ {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 1}{\sqrt{n}}} \\ 2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\ \end{eqnarray*} That is \[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\] } \ppart Express the following in closed form \[ {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q}.\] (Note that the lower indices are not constants.) \comment{ \bigskip \begin{eqnarray*} {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q} & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{q=p}^{\infty} y^{q-p}} & \\ & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{r=0}^{\infty} y^r} & \\ & = {\displaystyle \left( \sum_{p=1}^{\infty} x^py^p \right) \left( \sum_{r=0}^{\infty} y^r \right)} & \\ & = \left( \frac{xy}{1-xy}\right)\left( \frac{1}{1-y}\right). \end{eqnarray*} } \eparts \comment{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %4 \problem (10 points)\\ Unbeknownst to many, Leonardo Fibonacci had a brother Eduardo who invented the following sequence of numbers that he called {\em Eduardo} numbers: $$e_0 = 1$$ $$e_1 = 3$$ $$ \forall i \geq 2: e_i = e_{i-1} + e_{i-2}$$ Eduardo (who was not so good at math) made 2 conjectures about his numbers: $$C1: \forall i \geq 0: e_i = f_{i+1} + 2f_i$$ $$C2: \forall i \geq 0: e_i = f_{i+2} - f_i$$ where $f_i$ is the $i^{th}$ Fibonacci number ($f_0 = 0$, $f_1 = 1$, $f_n = f_{n-1}+f_{n-2}$ for all $n \geq 2$).\\ \def\longdash{\rule[.04in]{.1in}{.5pt}} Decide whether or not Eduardo's conjectures are true. Prove your answers. (Hint: do not repeat Eduardo's mistake by trying to solve the recurrence exactly $\longdash$ there is a much faster way to determine if each conjecture is true.)\\ \comment{ The first conjecture can be proven true by induction as follows:\\ {\em Base cases:} $e_o = 1 = f_1+2f_0, \,\,e_1 = 3 = 1+ 2 = f_2+2f_1$\\ {\em Induction step:} Suppose $e_i = f_{i+1}+2f_i$ for $i T(n)$). \ppart From the previous two parts, deduce tight ($\Theta$) bounds on $T(n)$ when $n$ is an arbitrary natural number. \end{problemparts} \comment{\bigskip \begin{eqnarray*} T(n) & = 4T(n/2) + 6n & \\ & = 4^2T(n/2^2) + 6(n + n/2) & \\ & = \ldots & \\ & = 4^iT(n/2^i) + 6(n + n/2 + \ldots + n/2^{i-1}) & \\ & = \ldots & \\ & = 4^{\log_2 n}T(1) + 6(n + n/2 + \ldots + n/2^{\log_2 n \ -1}) & \\ & = n^2T(1) + O(n) & \\ & = \Theta(n^2) \end{eqnarray*}} \problem Rank the following functions by order of growth; that is find an arrangement $g_1 = \alpha(g_2) = \alpha(g_3) = \ldots = \alpha(g_6)$ and state whether $\alpha$ is $o$ or $\Theta$ for each step. \begin{itemize} \item $n(\log_2 n)^5$ \item $n^3$ \item $n!$ \item $(n!)^2$ \item $n^n$ \item $3\cdot 8^{\log_2 n} + 4^{\log_2 n}$ \end{itemize} \comment{\bigskip \[ n(\log_2 n)^5 = o(n^3) = \Theta(3\cdot 8^{\log_2 n} + 4^{\log_2 n}) = o(n!) = o(n^n) = o((n!)^2). \] } \comment{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %2 \problem \\ For each of the following pairs of functions $f(n)$ and $g(n)$, fill in the blank with $O$, $\Omega$, $\Theta$, $o$ or $\omega$, depending on whether $f(n)= O(g(n))$, $f(n) = \Omega(g(n))$, $f(n) = \Theta(g(n))$, $f(n) = o(g(n))$ or $f(n) = \omega(g(n))$. If there is more than one relation between $f(n)$ and $g(n)$, write only the strongest one (a relation $X$ is stronger than another relation $Y$ if $X$ implies $Y$ but the converse does not hold). The first line is an example solution. Note: $\lg n = \log_2 n$.\\ \ \def\blank{\rule[-2pt]{.5in}{.5pt}} \[ \begin{array}{rcrl} 2n &=& \stackrel{\textstyle \Theta}{\blank} & (n) \\ &&&\\ \lg (n^3) &=& \stackrel{\textstyle \Theta}{\blank} & (\lg n)\\ &&&\\ n! &=& \stackrel{\textstyle \omega}{\blank} & (4^n)\\ &&&\\ 2^{\log_3 n} &=& \stackrel{\textstyle o}{\blank} & (n^2)\\ &&&\\ \sum_{i=1}^{n}{1/i} &=& \stackrel{\textstyle \omega}{\blank} & (1)\\ &&&\\ n^{4.01} &=& \stackrel{\textstyle \omega}{\blank} & (n^4 \lg n)\\ &&&\\ \sum_{i=n}^\infty {1/{i^2}} &=& \stackrel{\textstyle o}{\blank} & (1)\\ &&&\\ {n \choose 10}&=& \stackrel{\textstyle \Theta}{\blank} & (n^{10}) \\ &&&\\ 8^{\lg n} &=& \stackrel{\textstyle \Theta}{\blank} & (n^3) \end{array} \] } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %5 \problem Recurrences. \bparts \ppart Suppose that each pair of a genetically engineered species of rabbits left on an island produces two new pairs of rabbits at the age of one month and six new pairs of rabbits at the age of two months and every month afterwards. None of the rabbits ever die or leave the island. Find a recurrence relation for the number of {\em pairs} of rabbits on the island $n$ months after one newborn pair is left on the island. Do not solve the recurrence relation.\\ \\ \comment{ Let $N(t)$ be the number of pairs of rabbits after $t$ months. Then $N(0)=1$, $N(1)=3$, and we have that, for $t \geq 2$:\\ \begin{displaymath} N(t) = 7N(t-2) + 3(N(t-1)-N(t-2)) = 3N(t-1) + 4N(t-2) \end{displaymath}\\ \vspace{0.5in}} \ppart Solve the following inhomogeneous recurrence relation:\\ \begin{displaymath} f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2 \end {displaymath} The initial conditions are $f(0) = 5, f(1) = 26$.\\ \comment{ \\ The characteristic equation $r^2-6r+9$ has a repeated root $\alpha = 3$. Hence the homogeneous solution has the form $f_h(n) = A3^n+Bn3^n$, for some constants $A$ and $B$. To find a particular solution, we try $f_p(n) = K2^n$. Plugging into the difference equation gives:\\ \begin{math} K2^n = 6K2^{n-1} -9K2^{n-2}+2^n \Rightarrow K = \frac{6K}{2} - \frac{9K}{4} +1\\ \Rightarrow 4K= 12K-9K+4 \Rightarrow K = 4\\ \end{math}\\ Hence the complete solution has the form $f(n) = A3^n+Bn3^n +2^{n+2}$. We now use the initial conditions to solve for $A$ and $B$:\\ \begin{math} f(0) = 5 = A+4 \Rightarrow A = 1\\ f(10 = 26 = 3 + 3B +8 \Rightarrow B = 5\\ \end{math}\\ Hence the solution is $f(n) = 3^n + 5n3^n + 2^n, n \geq 2$. } \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %5 \problem Consider the following nuclear reaction. There is one particle of type $1$ at time instant $1$. Each particle of type $i$ existing at time $t$ undergoes fission to produce one particle of type $i+1$ and one of type $i+2$ at time instant $t+1$. \bparts \ppart Write and justify a recurrence for $f(i,t)$, the number of particles of type $i$ at time $t$. (Make sure to include the base cases for your recurrence.) \comment{ \bigskip Particles of types $i-2$ and $i-1$ at time $t-1$ give rise to particles of type $i$ at time $t$ and this is the only way that particles of type $i$ are formed at time $t$. Hence we get the recurrence \[ f(i,t) = f(i-1,t-1) + f(i-2,t-1), t > 1. \] The base case is \begin{itemize} \item $f(1,1) = 1$. \item $f(i,1) = 0, -\infty \leq i \leq \infty, i \not= 1$. \end{itemize} } \ppart Prove by induction that $f(i,t) = {t-1\choose i-t}$. (You do not need to reprove identities that were proven in class.) \comment{\bigskip (Note: Let $a$ be any nonnegative integer and $b$ be any integer. In what follows, we use the definition that ${a\choose b} = \frac{a!}{b!(a-b)!}$ when $a\geq b \geq 0$ and otherwise ${a\choose b} = 0$ when . Pascal's identity holds for this definition.) The proof is by induction on $t$. Let $P(t)$ be \[f(i,t) = {t-1\choose i-t}, \forall i.\] Base Case. $P(1)$ is true since \begin{itemize} \item $f(1,1) = {0\choose 0} = 1$. \item $f(i,1) = {0\choose i-1} = 0, -\infty \leq i \leq \infty, i \not= 1$. \end{itemize} Inductive step. Assume $P(t)$ is true. Consider $P(t+1)$. \begin{eqnarray*} f(i,t+1) & = f(i-1,t) + f(i-2,t) & \mbox{ by the recurrence from part a)}\\ & = {t-1\choose i-1-t} + {t-1\choose i-2-t} & \mbox{ by inductive hypothesis} \\ & = {t\choose i-1-t} & \mbox{ by Pascal's identity} \end{eqnarray*} Hence $P(t+1)$ is true. Thus $P(t)$ is true for all $t$ and we are done. } \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %4 \problem How many $6$-digit decimal numbers are there that do not contain ``$123$'' or ``$456$'' as a subsequence? (for purposes of this problem numbers may have leading $0$'s) \bigskip \comment{ Let \begin{itemize} \item $A$ be the set of all six-digit strings, using the digits $\{0, 1, \ldots, 9\}$. \item $B$ be the set of six-digit strings that contain the subsequence $123$. \item $C$ be the set of all six-digit strings that contain the subsequence $456$. \item $D$ be the set of all six-digit strings that do not contain $123$ or $456$. \end{itemize} We're interested in figuring out $| D |$. Since $$D = A - (B \cup C),$$ and $B \cup C \subseteq A$, we can use the inclusion-exclusion formula: $$| D | = | A | - |B \cup C| = | A | - | B | - | C | + | B \cap C |.$$ First, $|A| = 10^6$, since we can put any of ten digits in each of six places. Now, a string can contain $123$ in any of four positions; once this position is chosen, we have $1000$ choices for the remaining positions. However, this approach counts the string $123123$ twice, so the total size of $B$ is $$| B | = 4(1000) - 1 = 3999.$$ By the same reasoning, we get $$| C | = 3999.$$ Finally, there are only two strings in $B \cap C$, namely $123456$ and $456123$. Thus, $$| B \cap C | = 2.$$ Plugging this into our formula, we get $$| D | = 10^6 - 3999 - 3999 + 2 = 992004.$$ {\em (Common Mistakes: A lot of people forgot about the double-counting of $123123$ and $456456$, and so had $|B| = |C| = 4000$. Some people also argued that since $123$ can appear in one of only four places in the string, $|B| = 4$.)} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %6 \problem Binomial Coefficients. \bparts \ppart Prove, by direct calculation, that the following binomial identity is true for all $l,m,n$ such that $0 \leq l \leq m \leq n$ : \begin{displaymath} {n \choose m}{m \choose l} = {n \choose l}{n-l \choose m-l} \end{displaymath}\\ \comment{ We just expand the binomial coefficients and cancel:\\ \begin{math} {n \choose m}{n \choose l} = \frac{n!}{m!(n-m)!}\frac{m!}{l!(m-l)!} = \frac{n!}{(n-m)!}\frac{1}{l!(m-l)!}= \frac{n!}{l!(n-l)!}\frac{(n-l)!}{(m-l)!(n-m)!} = {n \choose l}{n-l \choose m-l} \end{math}\\ \vspace{0.5in}} \ppart Now prove the same identity combinatorially. Let $A$ be an $n$-element set. Explain how the left-hand and right-hand sides of the identity in part a) may be interpreted as the number of ways of choosing two subsets $B$ and $C$ of $A$, where $|B|=m$, $|C| =l$, and $C \subseteq B$.\\ \\ \comment{ The left hand side corresponds to first choosing $B$, then $C$. The number of ways of doing this is, using the product rule, ${n \choose m}{n \choose l}$. The right hand side corresponds to first choosing $C$, and then choosing $B-C$. The number of ways of doing this is, using the product rule, ${n \choose l}{n-l \choose m-l}$. Since both sides are equivalent to the number of ways of choosing subsets $B$ and $C$ such that $|B|=m$, $|C| =l$, and $C \subseteq B$, the identity holds.} \eparts \comment{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %2 \problem I have $n$ dollars that I wish to donate to $m$ charities in whole-dollar amounts (each charity gets a natural number of dollars, no fractions). \bparts \ppart In how many ways can I do this if I don't care how much each charity gets? \comment{\bigskip Simply insert $m-1$ bars into a string of $n$ one-dollar bills. Then the $i$-th charity gets the money between bars $i-1$ and $i$. This gives you ${n+m-1 \choose m-1 } $ ways to distribute the money. } \ppart In how many ways can I do this so that each charity gets at least \$ $10$? \comment{\bigskip First give 10 dollars to each charity, then distribute the remaining $n-10m$ dollars as in part a. This gives you ${n+m-1-10m \choose m-1}= {n-9m-1 \choose m-1}$ ways as long as $n\geq 10m$.} \eparts } \comment{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %7 \problem Four distinct children approach you on Halloween, requesting candy. You have ten pieces of candy to distribute among them. In how many different ways can you distribute the ten pieces if: (You must specify your answer as an integer, or as a ratio of products of integers, or as an integer raised to the power of an integer)\\ \bparts \ppart All the pieces are the same (Reese's Peanut-butter Cups$^{(TM)}$). No other restrictions.\\ \comment{ $${10+4-1 \choose 10} = {13 \choose 10} = \frac{13!}{3!10!}$$\\ \vspace{0.5in}} \ppart All the pieces are the same, and each child must receive at least one piece. No other restrictions.\\ \comment{ $${6+4-1 \choose 6} = {9 \choose 6} = \frac{9!}{3!6!}$$\\ \vspace{0.5in}} \ppart All the ten pieces are different. No other restrictions. \\ \comment{ $$4^{10}$$ } \comment{ \ppart Five pieces are Reese's Peanut-Butter Cups $^{(TM)}$ and the other five are Nestle's Crunch $^{(TM)}$. No other restrictions.\\ $${5+4-1 \choose 5}^2 = {8 \choose 5}^2 = (\frac{8!}{3!5!})^2$$\\ \vspace{0.5in} \ppart All the pieces are the same. No child gets more than $4$ pieces. No other restrictions.\\ We use the formula for $10$-combinations of $4$ elements with repetition with each element occurring fewer than $5$ times, and get:\\ $${13 \choose 3} - {4 \choose 1}{8 \choose 3} + {4 \choose 2}{3 \choose 3} = 68$$} \eparts } \end{problems} \end{document} % Local Variables: % mode: latex % TeX-master: t % End: \documentstyle[12pt,xypic,macpsfig,psfig,amssymb]{article} \input{macros-course} %\addtolength{\topmargin}{-.2in} %\setlength{\textheight}{9in} \setcounter{page}{0} \begin{document} \handout{pqsol2}{Solutions to Review for Quiz 2}{April 22, 1997} \long\def\comment#1{} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %6 \problem Prove that among any set of 150 natural numbers, there must be three numbers, $a$, $b$, and $c$, such that all the pairwise differences, $a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70. \bigskip \begin{proof} Use Pigeonhole. \\ {\bf Pigeons} The 150 numbers. \\ {\bf Holes} The natural numbers mod $70$. \\ There is some hole with $ \ceil{\frac{150}{70}} = 3$ pigeons, that is, three numbers $a,b,c$ that are equivalent modulo $70$. Then their differences are equivalent to $0$ modulo $70$, therefore they are divisible by $70$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %7 \problem For each of the following sets, decide whether the set is countable or uncountable and prove your answer. (If an answer to one part of the question follows from an answer you have already given to another part, then you need only show that is follows -- you don't need to prove the second part from scratch.) \\ \bparts \ppart The set $E$ of all the even natural numbers. \\ \bigskip This set is countable. The function $f(n) = 2n$ is a bijection from $\naturals$ to $E$. \bigskip \ppart The set of all subsets of $E$. \\ \bigskip This set is uncountable. The power set of any set has bigger cardinality than the original set. \\ \bigskip \ppart The set of all finite subsets of $E$. \\ \bigskip \ Let $S_{i} =$ { The set of all subsets of E with $i$ elements. } \\ Each of the $S_{i}$ is countable and the set under question is the countable union of all the $S_{i}$, therefore it is countable. \\ \bigskip \ppart The set of all even-size finite subsets of $E$. \\ \bigskip This set is countable, being a subset of the set in part (c). \\ \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %8 \problem The CS department has just completed a revamping of its curriculum. The following 10 courses are now required: 6.001, 6.002, 6.003, \dots , 6.009, and 6.042.\\ In addition, for every $i,j$, 6.00$i$ is a prerequisite of 6.00$j$ or 6.0j, if $i < j$ and $gcd(i,j) > 1$. \\ \vspace{.01in} \bparts \ppart Write down all the elements of the {\em prerequisite} relation. \\ \bigskip {\em prerequisite} $=$ \{ (6.002,6.004) , (6.002,6.006) , (6.002,6.008) , (6.002,6.0042) \\ (6.003,6.006) , (6.003,6.009) , (6.003,6.042) , (6.004,6.006) \\ (6.004,6.008) , (6.004,6.042) , (6.006,6.008) , (6.006,6.042) \\ (6.007,6.042) , (6.008,6.042) , (6.009,6.042) , (6.006,6.009) \} \\ \bigskip \ppart State whether this relation is reflexive, symmetric, transitive, antisymmetric. Is it an equivalence relation? \\ \bigskip The relation is antisymmetric, but nothing else. \\ \ppart Now consider the {\em taken before} relation which is defined to be the reflexive and transitive closure of the {\em prerequisite} relation. Draw the Hasse Diagram for the {\em taken before} relation. \\ $$\diagram 1 & 2\dline & 3\ddline \\ & 4\drline & \\ 5 & & 6\dlline\dline \\ 7\drline & 8\dline & 9\dlline \\ & 42& \\ \enddiagram$$ %\vspace{2.5in} \ppart The new regulations place no limit on how many courses a student can take in one term. What is the minimum number of terms required to complete all the required courses? Why? \\ \bigskip The minimum number of terms is $5$, which is the length of the critical path in the above Hasse diagram. \\ \bigskip \ppart Write down a maximum-size antichain in the partial order. What is the meaning of an antichain in terms of a student's schedule?\\ \bigskip 6.001, 6.002, 6.003, 6.005, 6.007. \\ An antichain is a list of subjects that a student can take at the same term. \\ \eparts \problem An {\em independent set} in a graph is a subset $S$ of the vertices such that no edge connects two vertices in $S$. Consider the following algorithm on a graph with vertices $v_1,\ldots,v_n$: \begin{tabbing} else \= else \= else \= else\kill initially no vertex is marked\\ {\bf for} $i=1$ to $n$\\ \> {\bf if} no neighbor of $v_i$ is marked {\bf then}\\ \> \> mark $v_i$\\ \end{tabbing} \begin{problemparts} \ppart Prove that when this algorithm terminates, the set of marked vertices is an independent set. By induction on $i$: The inductive hypothesis is: \\ $P(i):$ after the completion of the $i$th loop, the marked nodes form and independent set. Base Case: \\ $P(1)$: Since only $v_1$ is marked, it forms an independent set since it isn't connected to any other marked nodes. Inductive Step: $P(i) \rightarrow P(i+1)$ \\ At the beginning of the $i+1$st iteration, we know by the inductive hypothesis that the marked nodes form an independent set of $v_1 \ldots v_i$. We add $v_{i+1}$, only if it is not connected to any other $v_k$ that's marked, so the marked vertices of $v_1 \ldots v_{i+1}$ remain an independent set. Hence after completion of the $n$th iteration of the for loop, the marked vertices of $v_1 \ldots v_n$ form an independent set. \ppart {\bf (Optional)} Prove that the set of marked vertices is a {\em maximal} (under containment) independent set, in that adding any other vertex will make it not-independent. Assume for contradiction that there exists some vertex, $v_k$ that is not marked, yet is not connected to any marked vertex. When $i=k$ in the for loop, however, this vertex would have to have been marked since it wasn't connected to any marked vertex. So we have a contradiction, and there be no unmarked vertices with all unmarked neighbors. Therefore the marked vertices are a maximal independent set (note maximal, not maximum since we're not claiming that this set is the largest independent set). \end{problemparts} \problem We know that trees are bipartite because they contain no odd cycles. Give a direct proof that trees are bipartite by induction on the number of tree vertices. Base case: clearly a 1 vertex tree is bipartite. Inductive step: Suppose all $n$-vertex trees are bipartite---that is, can be legally colored with two colors red and green. Consider any $n+1$ vertex tree $T$. It has a leaf vertex $v$. If we remove $v$, we are left with an $n$-vertex tree that is bipartite by the IH. So we can legally color the remaining $n$ tree vertices red and green. Now put $v$ back. It is adjacent to only 1 node. If that node is red, make $v$ green, otherwise make $v$ red. This extends the legal coloring to $v$, so we have successfully colored $T$ with 2 colors, proving it is bipartite. \problem Sums. \bparts \ppart Give tight ($\Theta$) bounds for \[{\displaystyle \sum_{i=1}^n i^{1/2}}.\] \bigskip \begin{eqnarray*} {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\ {\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\ \sqrt{n}\leq 2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \leq 2\sqrt{n}\\ \end{eqnarray*} for all $n\geq 4$, that is \[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} \in \Theta(\sqrt{n}).\] \ppart Express the following in closed form \[ {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q}.\] (Note that the lower indices are not constants.) \bigskip \begin{eqnarray*} {\displaystyle \sum_{p=1}^{\infty} \sum_{q=p}^{\infty} x^py^q} & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{q=p}^{\infty} y^{q-p}} & \\ & = {\displaystyle \sum_{p=1}^{\infty} x^py^p \sum_{r=0}^{\infty} y^r} & \\ & = {\displaystyle \left( \sum_{p=1}^{\infty} x^py^p \right) \left( \sum_{r=0}^{\infty} y^r \right)} & \\ & = \left( \frac{xy}{1-xy}\right)\left( \frac{1}{1-y}\right). \end{eqnarray*} \eparts \comment{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %4 \problem (10 points)\\ Unbeknownst to many, Leonardo Fibonacci had a brother Eduardo who invented the following sequence of numbers that he called {\em Eduardo} numbers: $$e_0 = 1$$ $$e_1 = 3$$ $$ \forall i \geq 2: e_i = e_{i-1} + e_{i-2}$$ Eduardo (who was not so good at math) made 2 conjectures about his numbers: $$C1: \forall i \geq 0: e_i = f_{i+1} + 2f_i$$ $$C2: \forall i \geq 0: e_i = f_{i+2} - f_i$$ where $f_i$ is the $i^{th}$ Fibonacci number ($f_0 = 0$, $f_1 = 1$, $f_n = f_{n-1}+f_{n-2}$ for all $n \geq 2$).\\ \def\longdash{\rule[.04in]{.1in}{.5pt}} Decide whether or not Eduardo's conjectures are true. Prove your answers. (Hint: do not repeat Eduardo's mistake by trying to solve the recurrence exactly $\longdash$ there is a much faster way to determine if each conjecture is true.)\\ \comment{ The first conjecture can be proven true by induction as follows:\\ {\em Base cases:} $e_o = 1 = f_1+2f_0, \,\,e_1 = 3 = 1+ 2 = f_2+2f_1$\\ {\em Induction step:} Suppose $e_i = f_{i+1}+2f_i$ for $i 1. \] The base case is \begin{itemize} \item $f(1,1) = 1$. \item $f(i,1) = 0, -\infty < i < \infty, i \not= 1$. \end{itemize} \ppart Prove by induction that $f(i,t) = {t-1\choose i-t}$. (You do not need to reprove identities that were proven in class.) \bigskip (Note: Let $a$ be any nonnegative integer and $b$ be any integer. In what follows, we use the definition that ${a\choose b} = \frac{a!}{b!(a-b)!}$ when $a\geq b \geq 0$ and otherwise ${a\choose b} = 0$. Pascal's identity holds for this definition.) The proof is by induction on $t$. Let $P(t)$ be \[f(i,t) = {t-1\choose i-t}, \forall i.\] Base Case. $P(1)$ is true since \begin{itemize} \item $f(1,1) = {0\choose 0} = 1$. \item $f(i,1) = {0\choose i-1} = 0, -\infty < i < \infty, i \not= 1$. \end{itemize} Inductive step. Assume $P(t)$ is true. Consider $P(t+1)$. \begin{eqnarray*} f(i,t+1) & = f(i-1,t) + f(i-2,t) & \mbox{ by the recurrence from part a)}\\ & = {t-1\choose i-1-t} + {t-1\choose i-2-t} & \mbox{ by inductive hypothesis} \\ & = {t\choose i-1-t} & \mbox{ by Pascal's identity} \end{eqnarray*} Hence $P(t+1)$ is true. Thus $P(t)$ is true for all $t$ and we are done. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %4 \problem How many $6$-digit decimal numbers are there that do not contain ``$123$'' or ``$456$'' as a subsequence? (for purposes of this problem numbers may have leading $0$'s) \bigskip Let \begin{itemize} \item $A$ be the set of all six-digit strings, using the digits $\{0, 1, \ldots, 9\}$. \item $B$ be the set of six-digit strings that contain the subsequence $123$. \item $C$ be the set of all six-digit strings that contain the subsequence $456$. \item $D$ be the set of all six-digit strings that do not contain $123$ or $456$. \end{itemize} We're interested in figuring out $| D |$. Since $$D = A - (B \cup C),$$ and $B \cup C \subseteq A$, we can use the inclusion-exclusion formula: $$| D | = | A | - |B \cup C| = | A | - | B | - | C | + | B \cap C |.$$ First, $|A| = 10^6$, since we can put any of ten digits in each of six places. Now, a string can contain $123$ in any of four positions; once this position is chosen, we have $1000$ choices for the remaining positions. However, this approach counts the string $123123$ twice, so the total size of $B$ is $$| B | = 4(1000) - 1 = 3999.$$ By the same reasoning, we get $$| C | = 3999.$$ Finally, there are only two strings in $B \cap C$, namely $123456$ and $456123$. Thus, $$| B \cap C | = 2.$$ Plugging this into our formula, we get $$| D | = 10^6 - 3999 - 3999 + 2 = 992004.$$ {\em (Common Mistakes: A lot of people forgot about the double-counting of $123123$ and $456456$, and so had $|B| = |C| = 4000$. Some people also argued that since $123$ can appear in one of only four places in the string, $|B| = 4$.)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %6 \problem Binomial Coefficients. \bparts \ppart Prove, by direct calculation, that the following binomial identity is true for all $l,m,n$ such that $0 \leq l \leq m \leq n$ : \begin{displaymath} {n \choose m}{m \choose l} = {n \choose l}{n-l \choose m-l} \end{displaymath}\\ We just expand the binomial coefficients and cancel:\\ \begin{math} {n \choose m}{m \choose l} = \frac{n!}{m!(n-m)!}\frac{m!}{l!(m-l)!} = \frac{n!}{(n-m)!}\frac{1}{l!(m-l)!}= \frac{n!}{l!(n-l)!}\frac{(n-l)!}{(m-l)!(n-m)!} = {n \choose l}{n-l \choose m-l} \end{math}\\ \vspace{0.5in} \ppart Now prove the same identity combinatorially. Let $A$ be an $n$-element set. Explain how the left-hand and right-hand sides of the identity in part a) may be interpreted as the number of ways of choosing two subsets $B$ and $C$ of $A$, where $|B|=m$, $|C| =l$, and $C \subseteq B$.\\ \\ The left hand side corresponds to first choosing $B$, then $C$. The number of ways of doing this is, using the product rule, ${n \choose m}{n \choose l}$. The right hand side corresponds to first choosing $C$, and then choosing $B-C$. The number of ways of doing this is, using the product rule, ${n \choose l}{n-l \choose m-l}$. Since both sides are equivalent to the number of ways of choosing subsets $B$ and $C$ such that $|B|=m$, $|C| =l$, and $C \subseteq B$, the identity holds. \eparts \comment{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %2 \problem I have $n$ dollars that I wish to donate to $m$ charities in whole-dollar amounts (each charity gets a natural number of dollars, no fractions). \bparts \ppart In how many ways can I do this if I don't care how much each charity gets? \comment{\bigskip Simply insert $m-1$ bars into a string of $n$ one-dollar bills. Then the $i$-th charity gets the money between bars $i-1$ and $i$. This gives you ${n+m-1 \choose m-1 } $ ways to distribute the money. } \ppart In how many ways can I do this so that each charity gets at least \$ $10$? \comment{\bigskip First give 10 dollars to each charity, then distribute the remaining $n-10m$ dollars as in part a. This gives you ${n+m-1-10m \choose m-1}= {n-9m-1 \choose m-1}$ ways as long as $n\geq 10m$.} \eparts } \comment{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %7 \problem Four distinct children approach you on Halloween, requesting candy. You have ten pieces of candy to distribute among them. In how many different ways can you distribute the ten pieces if: (You must specify your answer as an integer, or as a ratio of products of integers, or as an integer raised to the power of an integer)\\ \bparts \ppart All the pieces are the same (Reese's Peanut-butter Cups$^{(TM)}$). No other restrictions.\\ \comment{ $${10+4-1 \choose 10} = {13 \choose 10} = \frac{13!}{3!10!}$$\\ \vspace{0.5in}} \ppart All the pieces are the same, and each child must receive at least one piece. No other restrictions.\\ \comment{ $${6+4-1 \choose 6} = {9 \choose 6} = \frac{9!}{3!6!}$$\\ \vspace{0.5in}} \ppart All the ten pieces are different. No other restrictions. \\ \comment{ $$4^{10}$$ } \comment{ \ppart Five pieces are Reese's Peanut-Butter Cups $^{(TM)}$ and the other five are Nestle's Crunch $^{(TM)}$. No other restrictions.\\ $${5+4-1 \choose 5}^2 = {8 \choose 5}^2 = (\frac{8!}{3!5!})^2$$\\ \vspace{0.5in} \ppart All the pieces are the same. No child gets more than $4$ pieces. No other restrictions.\\ We use the formula for $10$-combinations of $4$ elements with repetition with each element occurring fewer than $5$ times, and get:\\ $${13 \choose 3} - {4 \choose 1}{8 \choose 3} + {4 \choose 2}{3 \choose 3} = 68$$} \eparts } \end{problems} \end{document} % Local Variables: % mode: latex % TeX-master: t % End: \documentstyle[12pt,macpsfig,amssymb]{article} \input{macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \begin{document} \handout{pq1sol}{Practice Quiz 1 Solutions}{October 26, 1997} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem Use induction to prove that \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] whenever $n$ is a natural number. \bigskip Use induction to prove our proposition, P(n), \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] whenever $n$ is a natural number. {\bf Base Case:} $n = 0 $ The left side is an empty sum, so $0 = \left(\frac{0 \cdot 1}{2}\right)^2 = 0$. {\bf Inductive Step:} Show that $P(n) \rightarrow P(n+1)$. By the inductive hypothesis, we assume that \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] \begin{eqnarray*} 1^3 + 2^3 + \ldots + n^3 + (n+1)^3 \\ &= &\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\\ &= &\frac{n^2(n+1)^2 + 4(n+1)(n+1)^2}{4}\\ &= &\frac{(n^2+4n+4)(n+1)^2}{4}\\ &= &\left(\frac{(n+1)(n+2)}{2}\right)^2\\ \end{eqnarray*} And our hypothesis is proved. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 2 \problem Why can't you find an integer $x$ for which \[384\cdot x = 1 \pmod{566}?\] \bigskip This is equivalent to finding an integer $x$ such that there is some integer $y$ for which $384 \cdot x + 566 \cdot y = 1$. Since 384 and 566 are even, the LHS must be even, so no integers can give equality to 1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 3 \problem Prove the set identity \begin{math} ((A-B) \cup (B-A))^{c} = (A^{c} \cup B) \cap (A \cup B^{c}) \end{math} \bigskip Using the definition of set difference, both of De Morgan's Laws, and the commutativity of union (in that order): \begin{tabbing} $((A-B) \cup (B-A))^{c}$ \= $= ((A \cap B^c) \cup (B \cap A^c))^c$ \\ \> $= (A \cap B^c)^c \cap (B \cap A^c)^c$ \\ \> $= (A^c \cup B) \cap (B^c \cup A)$ \\ \> $= (A^c \cup B) \cap (A \cup B^c)$ \\ \end{tabbing} Alternatively, one can use the definitions of the operations. We need to prove $x$ is in the LHS if and only if it is in the RHS. $x \in ((A-B) \cup (B-A))^c$ means that $x \notin (A-B) \cup (B-A)$. This means that $x \notin A-B$ and $x \notin B-A$. So consider cases. If $x \in A$, then certainly $x \in A \cup B^c$. Furthermore, since by assumption $x \notin A-B$, we must have $x \in B$. Thus, $x \in B \cup A^c$. Putting these together shows $x \in (A \cup B^c) \cap (B \cup ^c)$. Now consider the other case. If $x \notin A$, meaning $x \in A^c$, then certainly $x \in A^c \cup B$. Also, (since $x \notin B-A$), we must have $x \notin B$. That is, $x \in B^c$. Therefore, $x \in B^c \cup A$. Thus, $x \in (A^c \cup B) \cap (B^c \cup A)$. This proves one direction; the other is similar (but you have to include it in the real quiz!). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 4 \problem Use the following tables to describe the properties of the various functions. Write yes or no in each box. Don't give proofs (it'd be too hard to squeeze them into the boxes). {\bf Pay careful attention} to the specified domains and ranges. \begin{itemize} \item $f:\naturals \rightarrow \naturals,\ f(x)=5x$. \item $g: \reals^+ \rightarrow \naturals,\ g(x)=\lfloor x \rfloor$. \item $h: \reals \rightarrow \reals^{+},\ h(x)=e^x$. \end{itemize} Give an inverse if one exists (under the given domain and range). \smallskip \begin{tabular}{l|c|c|c|c|} function & injective & surjective & inverse\\ \hline $f(x)=5x$ & yes & no & none \\ \hline $g(x) = \lfloor x \rfloor$ & no & yes & none \\ \hline $h(x)=e^x$ & yes & yes & ln($x$) \\ \hline \end{tabular} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 5 \problem Consider the following algorithm, which takes natural numbers $a$ and $b$, with $b > 0$, and returns an ordered pair of natural numbers. \begin{tabbing} else \= else \= else \= else \=\kill Algorithm Div$(a,b)$\\ \\ if $(a return $(0,a)$\\ else\\ \> $(q,r) \leftarrow $Div$(a-b,b)$\\ \> return $(q+1,r)$\\ \end{tabbing} \begin{problemparts} \problempart Prove Div terminates in at most $a + 1$ steps. We model the algorithm as a state machine with state $(q,r)$. The initial state is $(a,b)$. Termination occurs when the termination condition $(a 0$. %In this case, there is a recursive call Div$(a-b,b)$. %By the IH, this recursive call returns in at most $a - b +1$ steps. %Since $a - b < a$, this is at most $a + 1$ steps. \problempart Prove that Div returns the quotient and remainder of $a$ on division by $b$. Recall that the quotient and remainder of $a$ on division by $b$ are defined to be the unique integers $q$ and $r$ such that $a = qb + r$ and $0 \leq r < b$. These integers must exist by the Division Algorithm. We use strong induction on $a$. Base case: $a < b$. Then Div immediately returns (0, $a$). Since $a = 0 \cdot b + a$ and $0 \leq a < b$, these are the quotient and remainder of $a$ on division by $b$. Inductive step: $a \geq b$. Then $0 \leq a - b < a$. In this case, there is a recursive call Div$(a-b,b)$. By the IH, this recursive call returns the quotient and remainder of $a - b$ on division by $b$. So $a - b = qb + r$ and $0 \leq r < b$. Then $a = (q + 1)b + r$ and $0 \leq r < b$. So $q + 1$ and $r$ are the quotient and remainder of $a$ on division by $b$, and these are returned by Div. \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 6 \problem David is located at position $(1,0)$ on the two-dimensional $({\Bbb Z} \times {\Bbb Z})$ $x$-$y$ plane. His house is located at the origin. David wants to go home. But it is windy, and each time David takes a one-unit step east or west, he also gets blown a one-unit step north or south (he can pick which). \begin{tabular}{c|c|c|c|c|c|c|cc} \multicolumn{3}{r|}{$y$ }\\ \multicolumn{3}{c|}{ }\\ \cline{2-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} $x$&&&&&\\ \cline{1-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} \multicolumn{3}{c|}{ }\\ \multicolumn{3}{c|}{ }\\ \end{tabular} \begin{problemparts} \problempart On the grid above, mark with X's all the points that David can reach in one step. Mark with O's the points that David can reach in two steps. (The axes labeled $x$ and $y$ intersect at David's house.) \vspace{2in} \problempart Give an informal explanation for why David can never get home. David starts off with the sum of his coordinates (1 + 0 = 1) odd. Every time he moves, the parity of each coordinate changes, so the sum of his coordinates remains odd. Since the sum of the coordinates of his home (0 + 0 = 0) is even, he can never reach it. \newpage \problempart Describe a state machine that represents David's motion, and list its transitions. We introduce state variables $x, y \in {\Bbb Z}$. We designate exactly one start state: the one for which $x = 1$ and $y = 0$. The transitions are $(x,y) \rightarrow (x \pm 1, y\pm1)$. \problempart Prove that David can never get home. We use the following invariant: $x + y$ is odd for all reachable states. This is true for the start state (0 + 1 = 1). For each transition, the sum is modified either by $0$, $-2$, or $2$. Thus each transition increases $x + y$ by an even amount preserving the invariant. Since $x + y$ is even for the state corresponding to home, it is not a reachable state of our state machine. Thus David can never get home. \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 7 \problem Consider the following algorithm that takes an array (list) $A[1\ldots n]$ of numbers such that $A[1] 1)$\\ \> choose some $k$ with $i if $A[k] \le q$\\ \> \> $i \leftarrow k$\\ \> else\\ \> \> $j \leftarrow k$\\ Return $i$ \end{tabbing} \begin{problemparts} \ppart prove this function terminates Define a state machine whose state is $(i,j)$ and the initial state is $(1,n+1)$. Define the derived variable $f(i,j) = j-i$. Note that at each step we choose a $k$ such that $i < k < j$, and either set $j=k$ or $i=k$. Therefore $f$ is decreasing. Furthermore $f$ is non-negative since $j>i$. We conclude that the algorithm terminates in at most $n+1-1 = n$ steps. %We first prove (by induction on $l$) that after the $l$th pass %through the while loop, $j - i \leq n - l$. %{\bf Base Case:} $l = 0$. When we first reach the while loop, $j - i = n$ %because we just set $i$ to 1 and $j$ to $n + 1$. %{\bf Inductive Step:} By the IH, $j - i \leq n - l$ after the $l$th pass %through the while loop. During the ($l + 1$)st pass, either $i$ or %$j$ is moved to a value (that of $k$) strictly between their values %from the end of the $l$th pass. Thus the ($l + 1$)st pass decreases %$j - i$ by at least 1. So after the ($l + 1$)st pass through the %while loop, $j - i < n - l - 1 = n - (l + 1)$. \end{problemparts} Now suppose that $q=A[r]$ for some $r$. \begin{problemparts} \ppart State an invariant of the while loop relating $i,j$, and $r$. The invariant should be ``obviously provable by induction'' but you need not prove it. Our invariant is. $i \leq r < j$. \ppart Assuming the invariant, prove that Find returns $r$. When the loop terminates, $j - i \leq 1$ (from $j \leq i + 1$). Also, the invariant still holds. So $i \leq r < j \leq i + 1$. Since $i$ and $r$ are integers, $i = r$. Since $i$ is then returned, Find returns $r$. \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 8 \problem An infinite sequence of natural numbers $a_1, a_2, a_3$, \ldots is defined in such a way that $a_1 = 14, a_2 = 35$, and each later $a_i$, $i \geq 3$, is obtained using one of the following rules:\\ \vspace{.01in} {\bf Rule A} Choose any two preceding elements of the sequence and define $a_i$ to be their sum. \\ \vspace{.01in} {\bf Rule B} Choose any number $k \geq 1$ of preceding elements of the sequence,and define $a_i$ to be their product divided by $7^{k-1}$. \\ \vspace{.01in} Use the well-ordering principle to prove that every element in the sequence is a multiple of $7$. ({\it Hint: In case you have forgotten, the well-ordering principle says that every nonempty set of naturals has a smallest element.}) \bigskip \begin{proof} Let $S =$ \{all elements in the sequence that are not multiples of $7$ \}. \\ Assume that $S$ is nonempty. Then, by well-ordering, it has a smallest element $a_{n}$. \\ If $a_{n}$ is obtained by rule A, then $a_{n} = a_{i} + a_{j}$ for some $a_{i}$ and $a_{j}$ smaller than $a_{n}$. But then $a_{i}$ and $a_{j}$ are multiples of $7$ therefore $a_{n}$ has to be a multiple of $7$ also. \\ If $a_{n}$ is obtained by rule B, then there are $k$ smaller elements in the sequence ,that are multiples of $7$, so we can write them in the form $a_{k} = 7n_{k}$. $a_{n}$ is the product of the $a_k$ divided by $7^{k-1}$. Then we can write \\ \begin{displaymath} a_{n} = (\prod_{i=1}^{k} (7n_{i}))/7^{k-1} = 7(\prod_{i=1}^{k} n_{i}) \end{displaymath} Therefore $a_{n}$ is also a multiple of $7$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 9 \problem Prove that among any set of 150 natural numbers, there must be three numbers, $a$, $b$, and $c$, such that all the pairwise differences, $a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70. \bigskip \begin{proof} Use Pigeonhole. \\ {\bf Pigeons} The 150 numbers. \\ {\bf Holes} The natural numbers mod $70$. \\ There is some hole with $ \ceil{\frac{150}{70}} = 3$ pigeons, that is, three numbers $a,b,c$ that are equivalent modulo $70$. Then their differences are equivalent to $0$ modulo $70$, therefore they are divisible by $70$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 10 \problem For each of the following sets, either use diagonalization to prove that the set is uncountable, or else use dove-tailing or another technique to show that the set is countable. \\ (If an answer to one part of the question follows from an answer you have already given to another part, then you need only indicate this -- you don't need to give a direct proof of the part that follows.) \\ \bparts \ppart The set $E$ of all the even natural numbers. \\ \bigskip This set is countable. The function $f(n) = 2n$ is a bijection from $\naturals$to $E$. \bigskip \ppart The set of all subsets of $E$. \bigskip This set is uncountable. Suppose, for the purposes of contradiction, that it is countable and let $A_1,A_2,\ldots$ be an ordering of the subsets. Note that then there is a bijection from $E$ to the set of subsets of $E$ that sends the natural number $2i$ to the set $A_i$. Let $S$ be the subset of $E$ defined by $S = \{2i \in E | 2i \not\in A_i \}$. Let $n$ be the integer to which $S$ corresponds under the established bijection. Note that if $2n$ is in $S$, then it is not in $E$ which is a contradiction. If it is not in $S$, then $2n$ should be in $S$ by the definition of $S$, so we also have a contradiction. We conclude that the set of subsets of $E$ is uncountable. \bigskip \ppart The set of all finite subsets of $E$. \ Let $S_{i} =$ { The set of all subsets of E with $i$ elements. } Each of the $S_{i}$ is countable and the set under question is the countable union of all the $S_{i}$, therefore it is countable. \bigskip \ppart The set of all even-size finite subsets of $E$. \bigskip This set is countable, being a subset of the set in part (c). \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 11 \problem Give tight ($\Theta$) bounds for $$ \sum_{i=1}^n \frac{1}{\sqrt{i}}$$ You do not need to prove your answer formally, but you should show how you derived it. \bigskip We use the integration method for bounding summations.\\ \begin{eqnarray*} {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\ {\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\ 2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\ %{\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \%leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sq%rt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac%{2\sqrt{n} - 1}{\sqrt{n}}} \\ %2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1%}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\ \end{eqnarray*} That is \[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 12 \problem For each of the following pairs of functions $f(n)$ and $g(n)$, fill in the blank with $O$, $\Omega$, $\Theta$, $o$ or $\omega$, depending on whether $f(n)= O(g(n))$, $f(n) = \Omega(g(n))$, $f(n) = \Theta(g(n))$, $f(n) = o(g(n))$ or $f(n) = \omega(g(n))$. If there is more than one relation between $f(n)$ and $g(n)$, write only the strongest one (a relation $X$ is stronger than another relation $Y$ if $X$ implies $Y$ but the converse does not hold). The first line is an example solution. Note: $\lg n = \log_2 n$.\\ \ \def\blank{\rule[-2pt]{.5in}{.5pt}} \[ \begin{array}{rcrl} 2n &=& \stackrel{\textstyle \Theta}{\blank} & (n) \\ &&&\\ \lg (n^3) &=& \stackrel{\textstyle \Theta}{\blank} & (\lg n)\\ &&&\\ n! &=& \stackrel{\textstyle \omega}{\blank} & (4^n)\\ &&&\\ 2^{\log_3 n} &=& \stackrel{\textstyle o}{\blank} & (n^2)\\ &&&\\ \sum_{i=1}^{n}{1/i} &=& \stackrel{\textstyle \omega}{\blank} & (1)\\ &&&\\ n^{4.01} &=& \stackrel{\textstyle \omega}{\blank} & (n^4 \lg n)\\ &&&\\ \sum_{i=n}^\infty {1/{i^2}} &=& \stackrel{\textstyle o}{\blank} & (1)\\ &&&\\ {n \choose 10}&=& \stackrel{\textstyle \Theta}{\blank} & (n^{10}) \\ &&&\\ 8^{\lg n} &=& \stackrel{\textstyle \Theta}{\blank} & (n^3) \end{array} \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 13 \problem Find asymptotic bounds for the following recurrences. You may assume that $T(n)= \Theta(1)$ for $n \leq 1$ in each part.\\ \bparts \ppart $T(n)= 2T(\floor{n/2})+\Theta(n)$ $h(n) = \floor{n/2}-n/2$. $2(\frac{1}{2})^p = 1 \Rightarrow p = 1$. Hence we have that\\ \begin{displaymath} T(n) = \Theta(x(1+ \int_{1}^{x} \frac{u\,du}{u^2})) = \Theta(x(1+\ln x)) = \Theta(x\ln x) \end{displaymath} \vspace{0.5in} \ppart $T(n) = 4T(\floor{n/2+ \sqrt n})+ \Theta(n^2)$ $h(n) = \floor{n/2+ \sqrt n} - n/2$. $4(\frac{1}{2})^p = 1 \Rightarrow p = 2$. Hence we have that\\ \begin{displaymath} T(n) = \Theta(x^2(1+ \int_{1}^{x} \frac{u^2\,du}{u^3})) = \Theta(x^2(1+\ln x)) =\Theta(x^2\ln x) \end{displaymath} \vspace{0.5in} \ppart $T(n) = T(\lceil n/3 \rceil)+2T(\floor{n/4})+\Theta(n)$\\ We rewrite the recurrence as $T(n) = T(n/3 + (\lceil n/3 \rceil - n/3)) + 2T(n/4 + (\floor{n/4} -n/4)) + \Theta(n)$. By taking logs on both sides of $(\frac{1}{3})^p + 2(\frac{1}{4})^p = 1$ and simplifying, we get $p = \frac{\ln 2}{\ln 12} < 1$. Hence we have that\\ \begin{displaymath} T(n) = \Theta(x^p(1+ \int_{1}^{x} \frac{u\,du}{u^{p+1}})) = \Theta(x^p(1+x^{1-p}) = \Theta(x) \end{displaymath} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Problem 14 \problem In the following problem there is no direct connection between the two parts.\\ \bparts \ppart Suppose that each pair of a genetically engineered species of rabbits left on an island produces two new pairs of rabbits at the age of one month and six new pairs of rabbits at the age of two months and every month afterwards. None of the rabbits ever die or leave the island. Find a recurrence relation for the number of {\em pairs} of rabbits on the island $n$ months after one newborn pair is left on the island. Do not solve the recurrence relation. \bigskip Let $N(t)$ be the number of pairs of rabbits after $t$ months. Then $N(0)=1$, $N(1)=3$, and we have that, for $t \geq 2$:\\ \begin{displaymath} N(t) = 7N(t-2) + 3(N(t-1)-N(t-2)) = 3N(t-1) + 4N(t-2) \end{displaymath} \vspace{0.5in} \ppart Solve the following inhomogeneous recurrence relation: \begin{displaymath} f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2 \end {displaymath} The initial conditions are $f(0) = 5, f(1) = 26$. The characteristic equation $r^2-6r+9$ has a repeated root $\alpha = 3$. Hence the homogeneous solution has the form $f_h(n) = A3^n+Bn3^n$, for some constants $A$ and $B$. To find a particular solution, we try $f_p(n) = K2^n$. Plugging into the difference equation gives: \begin{math} K2^n = 6K2^{n-1} -9K2^{n-2}+2^n \Rightarrow K = \frac{6K}{2} - \frac{9K}{4} +1\\\Rightarrow 4K= 12K-9K+4 \Rightarrow K = 4\\ \end{math} Hence the complete solution has the form $f(n) = A3^n+Bn3^n +2^{n+2}$. We now use the initial conditions to solve for $A$ and $B$: \begin{math} f(0) = 5 = A+4 \Rightarrow A = 1\\ f(1) = 26 = 3 + 3B +8 \Rightarrow B = 5\\ \end{math} Hence the solution is $f(n) = 3^n + 5n3^n + 4 \cdot 2^n, n \geq 2$. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Problem 15 \problem{\bf Linear Recurrence\\} Give tight ($\Theta$) bounds for $T(n)$. Assume that $T(n)$ is constant for $n \leq 2$. \bparts \ppart $T(n) = 7T(n/3) + n^2$ Iterating, we see that \begin{eqnarray*} T(n) & = & n^2 + 7\left( \left( n\over 3\right)^2 + 7\left( \left( n\over 3^2\right)^2 + 7\left( \left( n\over 3^3\right)^2+\,\cdots \right)\right)\right)\\ & = & n^2 + 7\left( n\over 3\right)^2 + 7^2\left( n\over 3^2\right)^2 + 7^3\left( n\over 3^3\right)^2 + \cdots \\ & = & n^2 \left( 1+ \left( 7\over 3^2 \right) + \left( 7\over 3^2 \right)^2 + \left( 7\over 3^2 \right)^3 + \cdots\right)\\ & = & \Theta (n^2). \end{eqnarray*} since we have a decreasing geometric series. %\remove{ % \begin{quotation}\small % This is essentially what the ``master theorem'' says: % It requires that $f(n)=n^2$ be $\Omega(n^{\log_3 7+ \epsilon})$ % for some positive constant $\epsilon$ and $7(n/3)^2 \leq c(n^2)$ % for some postive constant $c<1$, both of which follow directly from % the fact that ${7 \over 3^2} < 1$. It concludes that $T(n)= \Theta(n^2)$.) % \end{quotation} %} \newpage \ppart $T(n) = 4T(n/3) + n$ We may again iterate as in part {\bf (a)} to see that \begin{eqnarray*} T(n) & = & n \left( 1+ \left( 4\over 3\right) + \left( 4\over 3\right)^2 + \cdots + \left( 4\over 3\right)^{\log_3 n} \right) \\ & = & \Theta \left( n \left( 4\over 3\right)^{\log_3 n} \right) \\ & = & \Theta \left( n \left( n \right)^{\log_3 4/3} \right) \\ & = & \Theta \left( n^{1+ \log_3 4/3} \right) \\ & = & \Theta \left( n^{\log_3 4} \right). \end{eqnarray*} \remove{ Again, this is essentially what the ``master theorem'' says: since $f(n)=n= O(n^{\log_3 4- \epsilon})$ for some positive constant $\epsilon$, $T(n)= \Theta(n^{\log_3 4})$. } \eparts \newpage \end{problems} \end{document} % LocalWords: Div David's \documentstyle[12pt,macpsfig,amssymb]{article} \input{macros-course} \addtolength{\topmargin}{-.2in} \setlength{\textheight}{9in} \setcounter{page}{0} \begin{document} \handout{pq1}{Practice Quiz 1}{October 22, 1997} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %DISCLAYMER \begin{large} This practice quiz contains problems from quizes of past semesters. There is some new material covered this semester that is not covered in this practice quiz. Also, expect the actual quiz to be much shorter (7 to 10 problems). \end{large} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 1 \problem Use induction to prove that \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] whenever $n$ is a natural number. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Problem 2 \problem Why can't you find an integer $x$ for which \[384\cdot x = 1 \pmod{566}?\] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 3 \problem Prove the set identity \begin{math} ((A-B) \cup (B-A))^{c} = (A^{c} \cup B) \cap (A \cup B^{c}) \end{math} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 4 \problem Use the following tables to describe the properties of the various functions. Write yes or no in each box. Don't give proofs (it'd be too hard to squeeze them into the boxes). {\bf Pay careful attention} to the specified domains and ranges. \begin{itemize} \item $f:\naturals \rightarrow \naturals,\ f(x)=5x$. \item $g: \reals^+ \rightarrow \naturals,\ g(x)=\lfloor x \rfloor$. \item $h: \reals \rightarrow \reals^{+},\ h(x)=e^x$. \end{itemize} Give an inverse if one exists (under the given domain and range). \smallskip \begin{tabular}{l|c|c|c|c|} function & injective & surjective & inverse\\ \hline $f(x)=5x$ & & &\\ \hline $g(x) = \lfloor x \rfloor$ & & &\\ \hline $h(x)=e^x$ & & & \\ \hline \end{tabular} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Problem 5 \problem Consider the following algorithm, which takes natural numbers $a$ and $b$, and returns an ordered pair of natural numbers. \begin{tabbing} else \= else \= else \= else \=\kill Algorithm Div$(a,b)$\\ \\ if $(a return $(0,a)$\\ else\\ \> $(q,r) \leftarrow $Div$(a-b,b)$\\ \> return $(q+1,r)$\\ \end{tabbing} \begin{problemparts} \problempart Prove Div terminates in at most $a$ steps. \problempart Prove that Div returns the quotient and remainder of $a$ on division by $b$. \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 6 \problem David is located at position $(1,0)$ on the two-dimensional $(\naturals \times \naturals)$ $x$-$y$ plane. His house is located at the origin. David wants to go home. But it is windy, and each time David takes a one-unit step east or west, he also gets blown a one-unit step north or south (he can pick which). \begin{tabular}{c|c|c|c|c|c|c|cc} \multicolumn{3}{r|}{$y$ }\\ \multicolumn{3}{c|}{ }\\ \cline{2-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} $x$&&&&&\\ \cline{1-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} \multicolumn{3}{c|}{ }\\ \multicolumn{3}{c|}{ }\\ \end{tabular} \begin{problemparts} \problempart On the grid above, mark with X's all the points that David can reach in one step. Mark with O's the points that David can reach in two steps. (The axes labeled $x$ and $y$ intersect at David's house.) \problempart Give an informal explanation for why David can never get home. \newpage \problempart Describe a state machine that represents David's motion, and list its transitions. \problempart Prove that David can never get home. \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 7 \problem Consider the following algorithm that takes an array (list) $A[1\ldots n]$ of numbers such that $A[1] 1)$\\ \> choose some $k$ with $i if $A[k] \le q$\\ \> \> $i \leftarrow k$\\ \> else\\ \> \> $j \leftarrow k$\\ Return $i$ \end{tabbing} \begin{problemparts} \ppart prove this function terminates \end{problemparts} Now suppose that $q=A[r]$ for some $r$. \begin{problemparts} \ppart State an invariant of the while loop relating $i,j$, and $r$. The invariant should be ``obviously provable by induction'' but you need not prove it. \ppart Assuming the invariant, prove that Find returns $r$. \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 8 \problem An infinite sequence of natural numbers $a_1, a_2, a_3$, \ldots is defined in such a way that $a_1 = 14, a_2 = 35$, and each later $a_i$, $i \geq 3$, is obtained using one of the following rules:\\ \vspace{.01in} {\bf Rule A} Choose any two preceding elements of the sequence and define $a_i$ to be their sum. \\ \vspace{.01in} {\bf Rule B} Choose any number $k \geq 1$ of preceding elements of the sequence,and define $a_i$ to be their product divided by $7^{k-1}$. \\ \vspace{.01in} Use the well-ordering principle to prove that every element in the sequence is a multiple of $7$. ({\it Hint: In case you have forgotten, the well-ordering principle says that every nonempty set of naturals has a smallest element.}) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 9 \problem Prove that among any set of 150 natural numbers, there must be three numbers, $a$, $b$, and $c$, such that all the pairwise differences, $a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 10 \problem For each of the following sets, either use diagonalization to prove that the set is uncountable, or else use dovetailing or another technique to show that the set is countable. \\ (If an answer to one part of the question follows from an answer you have already given to another part, then you need only indicate this -- you don't need to give a direct proof of the part that follows.) \\ \bparts \ppart The set $E$ of all the even natural numbers. \ppart The set of all subsets of $E$. \ppart The set of all finite subsets of $E$. \ppart The set of all even-size finite subsets of $E$. \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 11 \problem Give tight ($\Theta$) bounds for $$ \sum_{i=1}^n \frac{1}{\sqrt{i}}$$ You do not need to prove your answer formally, but you should show how you derived it. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 12 \problem For each of the following pairs of functions $f(n)$ and $g(n)$, fill in the blank with $O$, $\Omega$, $\Theta$, $o$ or $\omega$, depending on whether $f(n)= O(g(n))$, $f(n) = \Omega(g(n))$, $f(n) = \Theta(g(n))$, $f(n) = o(g(n))$ or $f(n) = \omega(g(n))$. If there is more than one relation between $f(n)$ and $g(n)$, write only the strongest one (a relation $X$ is stronger than another relation $Y$ if $X$ implies $Y$ but the converse does not hold). The first line is an example solution. Note: $\lg n = \log_2 n$.\\ \ \def\blank{\rule[-2pt]{.5in}{.5pt}} \[ \begin{array}{rcrl} 2n &=& \stackrel{\textstyle}{\blank} & (n) \\ %{\textstyle \Theta}{\blank} & (n) \\ &&&\\ \lg (n^3) &=& \stackrel{\textstyle}{\blank} & (\lg n)\\ &&&\\ n! &=& \stackrel{\textstyle}{\blank} & (4^n)\\ &&&\\ 2^{\log_3 n} &=& \stackrel{\textstyle}{\blank} & (n^2)\\ &&&\\ \sum_{i=1}^{n}{1/i} &=& \stackrel{\textstyle}{\blank} & (1)\\ &&&\\ n^{4.01} &=& \stackrel{\textstyle}{\blank} & (n^4 \lg n)\\ &&&\\ \sum_{i=n}^\infty {1/{i^2}} &=& \stackrel{\textstyle}{\blank} & (1)\\ &&&\\ {n \choose 10}&=& \stackrel{\textstyle}{\blank} & (n^{10}) \\ &&&\\ 8^{\lg n} &=& \stackrel{\textstyle}{\blank} & (n^3) \end{array} \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 13 \problem Find asymptotic bounds for the following recurrences. You may assume that $T(n)= \Theta(1)$ for $n \leq 1$ in each part.\\ \bparts \ppart $T(n)= 2T(\floor{n/2})+\Theta(n)$\\ \ppart $T(n) = 4T(\floor{n/2+ \sqrt n})+ \Theta(n^2)$\\ \ppart $T(n) = T(\lceil n/3 \rceil)+2T(\floor{n/4})+\Theta(n)$\\ \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 14 \problem In the following problem there is no direct connection between the two parts.\\ \bparts \ppart Suppose that each pair of a genetically engineered species of rabbits left on an island produces two new pairs of rabbits at the age of one month and six new pairs of rabbits at the age of two months and every month afterwards. None of the rabbits ever die or leave the island. Find a recurrence relation for the number of {\em pairs} of rabbits on the island $n$ months after one newborn pair is left on the island. Do not solve the recurrence relation.\\ \\ \ppart Solve the following inhomogeneous recurrence relation:\\ \begin{displaymath} f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2 \end {displaymath} \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{problems} \end{document} % LocalWords: Div David's \documentstyle[12pt,macpsfig,amssymb]{article} \input{macros-course} \begin{document} %\newcommand{\solution}[1]{} %\newcommand{\sol}[1]{} %\handout{pquiz}{Practice Quiz}{October 27, 1998} \newcommand{\solution}[1]{\bigskip #1} \newcommand{\sol}[1]{#1} \handout{pquizsol}{Practice Quiz Solutions}{October 30, 1998} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} %{\bf This practice quiz is the actual exam from Fall 1997. The quiz %this term will cover everything in the course up to and including the %lecture on Tuesday, October 27. This includes inclusion-exclusion, %the product rule, tree diagrams, and permutations, which are not %covered on this practice quiz. These topics are covered in Fake %Problem Set $7.5$.} \begin{problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem Use induction to prove that \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] whenever $n$ is a natural number. \solution{ Use induction to prove our proposition, P(n), \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] whenever $n$ is a natural number. {\bf Base Case:} $n = 0 $ The left side is an empty sum, so $0 = \left(\frac{0 \cdot 1}{2}\right)^2 = 0$. {\bf Inductive Step:} Show that $P(n) \rightarrow P(n+1)$. By the inductive hypothesis, we assume that \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] \begin{eqnarray*} 1^3 + 2^3 + \ldots + n^3 + (n+1)^3 \\ &= &\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\\ &= &\frac{n^2(n+1)^2 + 4(n+1)(n+1)^2}{4}\\ &= &\frac{(n^2+4n+4)(n+1)^2}{4}\\ &= &\left(\frac{(n+1)(n+2)}{2}\right)^2\\ \end{eqnarray*} And our hypothesis is proved. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 2 \problem Why can't you find an integer $x$ for which \[384\cdot x = 1 \pmod{566}?\] \solution{ This is equivalent to finding an integer $x$ such that there is some integer $y$ for which $384 \cdot x + 566 \cdot y = 1$. Since 384 and 566 are even, the LHS must be even, so no integers can give equality to 1. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 3 \problem Prove the set identity \begin{math} ((A-B) \cup (B-A))^{c} = (A^{c} \cup B) \cap (A \cup B^{c}) \end{math} \solution{ Using the definition of set difference, both of De Morgan's Laws, and the commutativity of union (in that order): \begin{tabbing} $((A-B) \cup (B-A))^{c}$ \= $= ((A \cap B^c) \cup (B \cap A^c))^c$ \\ \> $= (A \cap B^c)^c \cap (B \cap A^c)^c$ \\ \> $= (A^c \cup B) \cap (B^c \cup A)$ \\ \> $= (A^c \cup B) \cap (A \cup B^c)$ \\ \end{tabbing} Alternatively, one can use the definitions of the operations. We need to prove $x$ is in the LHS if and only if it is in the RHS. $x \in ((A-B) \cup (B-A))^c$ means that $x \notin (A-B) \cup (B-A)$. This means that $x \notin A-B$ and $x \notin B-A$. So consider cases. If $x \in A$, then certainly $x \in A \cup B^c$. Furthermore, since by assumption $x \notin A-B$, we must have $x \in B$. Thus, $x \in B \cup A^c$. Putting these together shows $x \in (A \cup B^c) \cap (B \cup ^c)$. Now consider the other case. If $x \notin A$, meaning $x \in A^c$, then certainly $x \in A^c \cup B$. Also, (since $x \notin B-A$), we must have $x \notin B$. That is, $x \in B^c$. Therefore, $x \in B^c \cup A$. Thus, $x \in (A^c \cup B) \cap (B^c \cup A)$. This proves one direction; the other is similar (but you have to include it in the real quiz!). } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 4 \problem Use the following tables to describe the properties of the various functions. Write yes or no in each box. Don't give proofs (it'd be too hard to squeeze them into the boxes). {\bf Pay careful attention} to the specified domains and ranges. \begin{itemize} \item $f:\naturals \rightarrow \naturals,\ f(x)=5x$. \item $g: \reals^+ \rightarrow \naturals,\ g(x)=\lfloor x \rfloor$. \item $h: \reals \rightarrow \reals^{+},\ h(x)=e^x$. \end{itemize} Give an inverse if one exists (under the given domain and range). \smallskip \begin{tabular}{l|c|c|c|c|} function & injective & surjective & inverse\\ \hline $f(x)=5x$ & \sol{yes} & \sol{no} & \sol{none} \\ \hline $g(x) = \lfloor x \rfloor$ & \sol{no} & \sol{yes} & \sol{none} \\ \hline $h(x)=e^x$ & \sol{yes} & \sol{yes} & \sol{ln($x$)} \\ \hline \end{tabular} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 5 \problem Consider the following algorithm, which takes natural numbers $a$ and $b$, with $b > 0$, and returns an ordered pair of natural numbers. \begin{tabbing} else \= else \= else \= else \=\kill Algorithm Div$(a,b)$\\ \\ if $(a return $(0,a)$\\ else\\ \> $(q,r) \leftarrow $Div$(a-b,b)$\\ \> return $(q+1,r)$\\ \end{tabbing} \begin{problemparts} \problempart Prove Div terminates in at most $a + 1$ steps. \solution{ We model the algorithm as a state machine with state $(q,r)$. The initial state is $(a,b)$. Termination occurs when the termination condition $(a 0$. %In this case, there is a recursive call Div$(a-b,b)$. %By the IH, this recursive call returns in at most $a - b +1$ steps. %Since $a - b < a$, this is at most $a + 1$ steps. \problempart Prove that Div returns the quotient and remainder of $a$ on division by $b$. \solution{ Recall that the quotient and remainder of $a$ on division by $b$ are defined to be the unique integers $q$ and $r$ such that $a = qb + r$ and $0 \leq r < b$. These integers must exist by the Division Algorithm. We use strong induction on $a$. Base case: $a < b$. Then Div immediately returns (0, $a$). Since $a = 0 \cdot b + a$ and $0 \leq a < b$, these are the quotient and remainder of $a$ on division by $b$. Inductive step: $a \geq b$. Then $0 \leq a - b < a$. In this case, there is a recursive call Div$(a-b,b)$. By the IH, this recursive call returns the quotient and remainder of $a - b$ on division by $b$. So $a - b = qb + r$ and $0 \leq r < b$. Then $a = (q + 1)b + r$ and $0 \leq r < b$. So $q + 1$ and $r$ are the quotient and remainder of $a$ on division by $b$, and these are returned by Div. } \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 6 \problem David is located at position $(1,0)$ on the two-dimensional $({\Bbb Z} \times {\Bbb Z})$ $x$-$y$ plane. His house is located at the origin. David wants to go home. But it is windy, and each time David takes a one-unit step east or west, he also gets blown a one-unit step north or south (he can pick which). \begin{tabular}{c|c|c|c|c|c|c|cc} \multicolumn{3}{r|}{$y$ }\\ \multicolumn{3}{c|}{ }\\ \cline{2-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} $x$&&&&&\\ \cline{1-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} &&&&&\\ \cline{2-6} \multicolumn{3}{c|}{ }\\ \multicolumn{3}{c|}{ }\\ \end{tabular} \begin{problemparts} \problempart On the grid above, mark with X's all the points that David can reach in one step. Mark with O's the points that David can reach in two steps. (The axes labeled $x$ and $y$ intersect at David's house.) \problempart Give an informal explanation for why David can never get home. \solution{ David starts off with the sum of his coordinates (1 + 0 = 1) odd. Every time he moves, the parity of each coordinate changes, so the sum of his coordinates remains odd. Since the sum of the coordinates of his home (0 + 0 = 0) is even, he can never reach it. } \problempart Describe a state machine that represents David's motion, and list its transitions. \solution{ We introduce state variables $x, y \in {\Bbb Z}$. We designate exactly one start state: the one for which $x = 1$ and $y = 0$. The transitions are $(x,y) \rightarrow (x \pm 1, y\pm1)$. } \problempart Prove that David can never get home. \solution{ We use the following invariant: $x + y$ is odd for all reachable states. This is true for the start state (0 + 1 = 1). For each transition, the sum is modified either by $0$, $-2$, or $2$. Thus each transition increases $x + y$ by an even amount preserving the invariant. Since $x + y$ is even for the state corresponding to home, it is not a reachable state of our state machine. Thus David can never get home. } \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 7 \problem Consider the following algorithm that takes an array (list) $A[1\ldots n]$ of numbers such that $A[1] 1)$\\ \> choose some $k$ with $i if $A[k] \le q$\\ \> \> $i \leftarrow k$\\ \> else\\ \> \> $j \leftarrow k$\\ Return $i$ \end{tabbing} \begin{problemparts} \ppart prove this function terminates \solution{ Define a state machine whose state is $(i,j)$ and the initial state is $(1,n+1)$. Define the derived variable $f(i,j) = j-i$. Note that at each step we choose a $k$ such that $i < k < j$, and either set $j=k$ or $i=k$. Therefore $f$ is decreasing. Furthermore $f$ is non-negative since $j>i$. We conclude that the algorithm terminates in at most $n+1-1 = n$ steps. %We first prove (by induction on $l$) that after the $l$th pass %through the while loop, $j - i \leq n - l$. %{\bf Base Case:} $l = 0$. When we first reach the while loop, $j - i = n$ %because we just set $i$ to 1 and $j$ to $n + 1$. %{\bf Inductive Step:} By the IH, $j - i \leq n - l$ after the $l$th pass %through the while loop. During the ($l + 1$)st pass, either $i$ or %$j$ is moved to a value (that of $k$) strictly between their values %from the end of the $l$th pass. Thus the ($l + 1$)st pass decreases %$j - i$ by at least 1. So after the ($l + 1$)st pass through the %while loop, $j - i < n - l - 1 = n - (l + 1)$. } \end{problemparts} Now suppose that $q=A[r]$ for some $r$. \begin{problemparts} \ppart State an invariant of the while loop relating $i,j$, and $r$. The invariant should be ``obviously provable by induction'' but you need not prove it. \solution{ Our invariant is $i \leq r < j$. } \ppart Assuming the invariant, prove that Find returns $r$. \solution{ When the loop terminates, $j - i \leq 1$ (from $j \leq i + 1$). Also, the invariant still holds. So $i \leq r < j \leq i + 1$. Since $i$ and $r$ are integers, $i = r$. Since $i$ is then returned, Find returns $r$. } \end{problemparts} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 8 \problem An infinite sequence of natural numbers $a_1, a_2, a_3$, \ldots is defined in such a way that $a_1 = 14, a_2 = 35$, and each later $a_i$, $i \geq 3$, is obtained using one of the following rules:\\ {\bf Rule A} Choose any two preceding elements of the sequence and define $a_i$ to be their sum. \\ {\bf Rule B} Choose any number $k \geq 1$ of preceding elements of the sequence,and define $a_i$ to be their product divided by $7^{k-1}$. \\ Use the well-ordering principle to prove that every element in the sequence is a multiple of $7$. ({\it Hint: In case you have forgotten, the well-ordering principle says that every nonempty set of naturals has a smallest element.}) \solution{ \begin{proof} Let $S =$ \{all elements in the sequence that are not multiples of $7$ \}. \\ Assume that $S$ is nonempty. Then, by well-ordering, it has a smallest element $a_{n}$. \\ If $a_{n}$ is obtained by rule A, then $a_{n} = a_{i} + a_{j}$ for some $a_{i}$ and $a_{j}$ smaller than $a_{n}$. But then $a_{i}$ and $a_{j}$ are multiples of $7$ therefore $a_{n}$ has to be a multiple of $7$ also. \\ If $a_{n}$ is obtained by rule B, then there are $k$ smaller elements in the sequence ,that are multiples of $7$, so we can write them in the form $a_{k} = 7n_{k}$. $a_{n}$ is the product of the $a_k$ divided by $7^{k-1}$. Then we can write \\ \begin{displaymath} a_{n} = (\prod_{i=1}^{k} (7n_{i}))/7^{k-1} = 7(\prod_{i=1}^{k} n_{i}) \end{displaymath} Therefore $a_{n}$ is also a multiple of $7$. \end{proof} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 9 \problem Prove that among any set of 150 natural numbers, there must be three numbers, $a$, $b$, and $c$, such that all the pairwise differences, $a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70. \solution{ \begin{proof} Use Pigeonhole. \\ {\bf Pigeons} The 150 numbers. \\ {\bf Holes} The natural numbers mod $70$. \\ There is some hole with $ \ceil{\frac{150}{70}} = 3$ pigeons, that is, three numbers $a,b,c$ that are equivalent modulo $70$. Then their differences are equivalent to $0$ modulo $70$, therefore they are divisible by $70$. \end{proof} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 10 \problem For each of the following sets, either use diagonalization to prove that the set is uncountable, or else use dove-tailing or another technique to show that the set is countable. \\ (If an answer to one part of the question follows from an answer you have already given to another part, then you need only indicate this -- you don't need to give a direct proof of the part that follows.) \\ \bparts \ppart The set $E$ of all the even natural numbers. \solution{ This set is countable. The function $f(n) = 2n$ is a bijection from $\naturals$to $E$. } \ppart The set of all subsets of $E$. \solution{ This set is uncountable. Suppose, for the purposes of contradiction, that it is countable and let $A_1,A_2,\ldots$ be an ordering of the subsets. Note that then there is a bijection from $E$ to the set of subsets of $E$ that sends the natural number $2i$ to the set $A_i$. Let $S$ be the subset of $E$ defined by $S = \{2i \in E | 2i \not\in A_i \}$. Let $n$ be the integer to which $S$ corresponds under the established bijection. Note that if $2n$ is in $S$, then it is not in $E$ which is a contradiction. If it is not in $S$, then $2n$ should be in $S$ by the definition of $S$, so we also have a contradiction. We conclude that the set of subsets of $E$ is uncountable. } \ppart The set of all finite subsets of $E$. \solution{ Let $S_{i} =$ { The set of all subsets of E with $i$ elements. } Each of the $S_{i}$ is countable and the set under question is the countable union of all the $S_{i}$, therefore it is countable. } \ppart The set of all even-size finite subsets of $E$. \solution{ This set is countable, being a subset of the set in part (c). } \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 11 \problem Give tight ($\Theta$) bounds for $$ \sum_{i=1}^n \frac{1}{\sqrt{i}}$$ You do not need to prove your answer formally, but you should show how you derived it. \solution{ We use the integration method for bounding summations.\\ \begin{eqnarray*} {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\ {\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\ 2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\ %{\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \%leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sq%rt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac%{2\sqrt{n} - 1}{\sqrt{n}}} \\ %2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1%}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\ \end{eqnarray*} That is \[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\] } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 12 \problem For each of the following pairs of functions $f(n)$ and $g(n)$, fill in the blank with $O$, $\Omega$, $\Theta$, $o$ or $\omega$, depending on whether $f(n)= O(g(n))$, $f(n) = \Omega(g(n))$, $f(n) = \Theta(g(n))$, $f(n) = o(g(n))$ or $f(n) = \omega(g(n))$. If there is more than one relation between $f(n)$ and $g(n)$, write only the strongest one (a relation $X$ is stronger than another relation $Y$ if $X$ implies $Y$ but the converse does not hold). The first line is an example solution. Note: $\lg n = \log_2 n$.\\ \ \def\blank{\rule[-2pt]{.5in}{.5pt}} \[ \begin{array}{rcrl} 2n &=& \stackrel{\sol{\textstyle \Theta}}{\blank} & (n) \\ &&&\\ \lg (n^3) &=& \stackrel{\sol{\textstyle \Theta}}{\blank} & (\lg n)\\ &&&\\ n! &=& \stackrel{\sol{\textstyle \omega}}{\blank} & (4^n)\\ &&&\\ 2^{\log_3 n} &=& \stackrel{\sol{\textstyle o}}{\blank} & (n^2)\\ &&&\\ \sum_{i=1}^{n}{1/i} &=& \stackrel{\sol{\textstyle \omega}}{\blank} & (1)\\ &&&\\ n^{4.01} &=& \stackrel{\sol{\textstyle \omega}}{\blank} & (n^4 \lg n)\\ &&&\\ \sum_{i=n}^\infty {1/{i^2}} &=& \stackrel{\sol{\textstyle o}}{\blank} & (1)\\ &&&\\ {n \choose 10}&=& \stackrel{\sol{\textstyle \Theta}}{\blank} & (n^{10}) \\ &&&\\ 8^{\lg n} &=& \stackrel{\sol{\textstyle \Theta}}{\blank} & (n^3) \end{array} \] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %problem 13 \problem Find asymptotic bounds for the following recurrences. You may assume that $T(n)= \Theta(1)$ for $n \leq 1$ in each part. \bparts \ppart $T(n)= 2T(\floor{n/2})+\Theta(n)$ \solution{ $h(n) = \floor{n/2}-n/2$. $2(\frac{1}{2})^p = 1 \Rightarrow p = 1$. Hence we have that\\ \begin{displaymath} T(n) = \Theta(x(1+ \int_{1}^{x} \frac{u\,du}{u^2})) = \Theta(x(1+\ln x)) = \Theta(x\ln x) \end{displaymath} } \ppart $T(n) = 4T(\floor{n/2+ \sqrt n})+ \Theta(n^2)$ \solution{ $h(n) = \floor{n/2+ \sqrt n} - n/2$. $4(\frac{1}{2})^p = 1 \Rightarrow p = 2$. Hence we have that\\ \begin{displaymath} T(n) = \Theta(x^2(1+ \int_{1}^{x} \frac{u^2\,du}{u^3})) = \Theta(x^2(1+\ln x)) =\Theta(x^2\ln x) \end{displaymath} } \ppart $T(n) = T(\lceil n/3 \rceil)+2T(\floor{n/4})+\Theta(n)$\\ \solution{ We rewrite the recurrence as $T(n) = T(n/3 + (\lceil n/3 \rceil - n/3)) + 2T(n/4 + (\floor{n/4} -n/4)) + \Theta(n)$. By taking logs on both sides of $(\frac{1}{3})^p + 2(\frac{1}{4})^p = 1$ and simplifying, we get $p = \frac{\ln 2}{\ln 12} < 1$. Hence we have that\\ \begin{displaymath} T(n) = \Theta(x^p(1+ \int_{1}^{x} \frac{u\,du}{u^{p+1}})) = \Theta(x^p(1+x^{1-p})) = \Theta(x) \end{displaymath} } \eparts %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Problem 14 \problem In the following problem there is no direct connection between the two parts.\\ \bparts \ppart Suppose that each pair of a genetically engineered species of rabbits left on an island produces two new pairs of rabbits at the age of one month and six new pairs of rabbits at the age of two months and every month afterwards. None of the rabbits ever die or leave the island. Find a recurrence relation for the number of {\em pairs} of rabbits on the island $n$ months after one newborn pair is left on the island. Do not solve the recurrence relation. \solution{ Let $N(t)$ be the number of pairs of rabbits after $t$ months. Then $N(0)=1$, $N(1)=3$, and we have that, for $t \geq 2$:\\ \begin{displaymath} N(t) = 7N(t-2) + 3(N(t-1)-N(t-2)) = 3N(t-1) + 4N(t-2) \end{displaymath} } \ppart Solve the following inhomogeneous recurrence relation: \begin{displaymath} f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2 \end {displaymath} \solution{ The initial conditions are $f(0) = 5, f(1) = 26$. The characteristic equation $r^2-6r+9$ has a repeated root $\alpha = 3$. Hence the homogeneous solution has the form $f_h(n) = A3^n+Bn3^n$, for some constants $A$ and $B$. To find a particular solution, we try $f_p(n) = K2^n$. Plugging into the difference equation gives: \begin{math} K2^n = 6K2^{n-1} -9K2^{n-2}+2^n \Rightarrow K = \frac{6K}{2} - \frac{9K}{4} +1\\\Rightarrow 4K= 12K-9K+4 \Rightarrow K = 4\\ \end{math} Hence the complete solution has the form $f(n) = A3^n+Bn3^n +2^{n+2}$. We now use the initial conditions to solve for $A$ and $B$: \begin{math} f(0) = 5 = A+4 \Rightarrow A = 1\\ f(1) = 26 = 3 + 3B +8 \Rightarrow B = 5\\ \end{math} Hence the solution is $f(n) = 3^n + 5n3^n + 4 \cdot 2^n, n \geq 2$. } \eparts \end{problems} \end{document} This file krypted Wed Jan 12 18:22:59 2000 o~{F*4۫M+)腬9ZލNIHH"i!G o?CZ6K X)i ^Lhog QW1>8F ^NS 4}fgYKKEYm^: {XY`KЕl9db_f :zpf؝4CzAqw͂ //5v^{齖WĨ.)"u'S|(oc[~หz(?օ+N܏eb:89=Yȋ{Pn(8}'Ql󩢽m&Ɔ! - 7N ЬlY%MjnKgH?3L8 8F(S[iGo@V+mqDmc507'ZsǦ#F;'Dt2"6c;Cj6fzDٚWWt\`lbkۖ?aD\Yo1ϑZ8]KV?YyAqՓɗCr}ɡ*k{ s.@wǸ%ƀ J rMKD j΀Z/VBr%ZʚM7VeMgbZjB$6EGnH;5q/HgrW}36H O DtT^$9ɜ͖vpO~H2䋯j_bHP,2E8 nǹD{xY>_z(H\SEBtaѺ٥``km*r cZHFNxbb5e_bdXL4kWH2Qq`0DIRQMkd@O  Qʀ)8)(QV'at;G_{$O:M { Rԏeq&PhEGȅƱx$j)PJ%()+Ph/PgYr*QM_d\F$3zs-zo+l;mqsY~fUDp}5`|pCH$M '.pK&IއNÜ[^&mZSq(m0Pc׺1=-Cm](+\%$Z͛>7Їؖ3lkH __S*#".3҄,XԦeda(w׈Mۼ/1I U] urհu{,oRG6p?ityJA DڤpEsEF` ?>]lVELw.VK Kw[w!v $YXD(COa2Z v'v|g@JT?Y4Q#x= mζq!!\J8æPYPY!Ü2QCJ6`ڏXLI5׌DHE1ƥGd:\>t Ih\EWx"}pR; 7O1t\cmQ.vM_h3J#=0sӇps4,pf~Ň5B %N( ʕU*2(95 WK2g C8k FQYm(ɄMaq: jM.[gmBynܢF8=o9LV̎rs6Z>/̨d?1x%~ oԯ'+Nv=+W5JChZUZT/dyq&N]08>)Y ;IOCsKaI;[{ )R-ˋ,kDZ͡%B8}fݝr).O_ǑV$ ą=J{ q}Fe%\*%ْOB|؞JiDt_ sjm7KRۉ\{xbϬx 7)CsNL*|(HX0'2#Ĥn*$ؚt썭CPR7 .?tF# BrOH%X"B#l־M8"ZӇބ1 `9 I7Q + y,^0m邝p]bJpO! v)[K>^xV=;9s xSPEq1\Hx>[}*hbg( ݀S `V a V.~HB}r}ÞEt#wfʙKR/ѯ+\d൓ jaeJtխ58:^c䝭ɹCG1Q>7\@NmdGO܉6yXO[pJtf,:ǹfb WY?Jnדp"1:vt2 "KK9.DfNuߋH.['0vN;` )aZcEҢjMؠL%+ǔ ar Ah?f7#ȏfЬN4+HmsŻZD ᕿQÉ1?4ISG/ߨDaTSޝVkAGJ;9ρY*Rogp!@bM[#x*9yi*4GOo 90!^ib/b(>nX'Á+!>_k_7&q;^1ܻ]Hk@*"FЕT,İp>ȶrOм^}i!kPqO9(983ҿ1e.dk;>F۰@n3R [We[G*zԼkaˀhZ:0TT)ZL%lSӯ LGݫC:92]S9{M|A^LBHcBk3|v 4z)(X#wB_y8}߲o|}N*{H ɼI D#/3ߢQGNj{qU9ZoRSIZAzz=X--sà=ȥ3*im^^F49CQ~&$A Nt3AouAhSҭ`Gk@*X2AhmeK߽+5ےC,Z])eo`%DQ 2T(UZ̯uuVX&Eoҿ:pX](.me++T'~AR4lﭰrK<^ץ{A9`һIP$tҫД +róPpK#'+Z gGah^8x;Fy.E k#Q v%y=&Q*)OizyviVֿY7*Dc FHJ" &~U\yP.@7@ -)-HW˫?'«U,D56#[%o?e@Qg6ev_Wf?5>F!AGwSS&VJ̾u9CY5>cSt:;cN+ *uLC2oU=gi\ |?-ؗ&ѴnPʴWbfcULPBeTCN~zZiuPJ ]ȆqdNs;h9jp w#")29lwE\fV5X`u}.yєC~F)C[~#Ŷ~Nm*W m5"@>b\;|yW11>+P/38>Ao {LBq}{dv+Lލ^NHMn@Hdb|sa6t8,gtm$/Gsз(Tuw!3Y6 DҢԅpO$x \ҳ`J;O¬i'Son#51WP9pIlUBAѠ94˦8P`2XrE_?A>9#1һ|Q|,ܓMlŶɈ4tNmUa\pegE.a0]yp~c 4"!V$EE0=uXwsF]۵ |:8c3Yy$=3rctDO4COzyWz'ڔ# 8Ha%')LaZs9ƅb;v :U1:Q,GP?]I/s14"'u}W7Pm6*|D7JE ؏ua ^{ mapaG?Rh2'2ut3e;%@u,-snF I4D*GwvQD6&PMNw0 E%6,uVf #K874dяB3+/^uby+6u;Zۦ+ئ5?S^^-b4Лj$c٭Sd¥w5iRˠ!$ՎF vx0Ut{إ>.fJz=/׵{"z?ΝG>r$7˰'sgfs*$㝂A k[r|]A ʪ:LK =<5M$F2O5yxKH1 =F\AB8Lr[`zx7=A"fs|f( ؀*8-S]bQL&C7uw7ϰ$Y8a(np>v$I}opgڗ(LBk3{:[n|a)ߠaYQhWIGYKD=WAaO4e#j'#%ۿ.ޑ˅pU%UI]K>drߣ/x$}vnj.-u1߱uVH,d?j2iimX4u` @fʿ ĘiB5:UYMF(^)I*L&}y|swۇC4p>yR]dgv.~()I^0)|]q7Pns:^SQ(~Q[r(>~(%F%_KaDTxF~YwDڳrE8~ߤcמx1>5$1ͧ_} n5+K6W_rU<!:֊+JuH(7FF 6JvwG6oNS03*̧΅8*,L‡*GNWȿƎ/Gk\\r"U/*MD_R/]2zyIzۨ/:W@A)Ka,_+<wų `J.vG1R=~jǔg+L=Q:Zi hu=ha1:k= OdJCPnCPCc|MڅCнYzj}(]E;|.p$+:Z"\D3@ 蔶L"kh۸͝@(7Maoλd)]sJP*# Na%,/2d;2?F 1;߿80wc4z$^+11!s]ZsST٥-gכ `NRۄȺU5Y)W'snFaV\D#s[',CtVͫ|M܍-B~flpEIztZ"8dꅺW`rrS TNˆGKJKJ \^x \Ԥyp>X9VBl=%H1!Gy6*gv$Yof߅gY=_UЄ J<m6Jߨ}) P?ܚ)k˾3;~GU57ښ!-쉓bQ"?% uq6ݧ$ql~aq'8)ǻzE٭[bH?i쒍_w/kDhK#s*tk`Ɓ`Mx#'A&?1!Z|tװ)&(Lj6+[pM;lzuHT[:d8죿eFv)A\+SXg nFI⿤Yu6AI8/4`8 PJv*Pc)HpB?F:8y4+DdJ.nߨ*K2U-s2Yh:c[sm~x1mmD %0p)_im[uɇL*|`ǻ$VaX5,.PۑR[N8j]J.t&j3p秪CR‡w1 kT7~u EXEPq\Ж}5$NaeM0 t[feuy \ r,`ǝR?R.?ݯPl`5|+H7=b򹵝}S& H~A-%"UwY+mwԦ|zfXbzZdo-8|tL$Yֵk&@ A3w[GJI#: Wp"YZI G!352MUZ/K'l#LcFҿ c'H>i0J&pjotq};p kLP jEpϱ9s(=;äo?_evR!=a"/9ςa ז1%ړlh2h*Ԃ{}H: AI( WemetJ~\CMAv0z._~5thF *H-xqRRr1m,88Y \^lnzMf 8Qr2`ps(2Us .hYc)d33}1񲢢bh׶coIh4Wk+/IE\^rdS˭@uN-RE1 ^硶>Lj4\T PAh`6֚}=ok oJYef\bBr%]!3:mIf >fPR$l͛%3W C@=%x/qEJo$@&3qH,Px$:pPRr&" kL-PvmiwFdW{֓"ӈGZ;f;`{ӭ9_4a{yD|_ !KA H Sz}[TÍ_+{LiTbl~!PאUd l]Z~:E%4 |aK NhR)U{Xyc/aE` Z馛2״n%㓵lS^Ff4fވ_rvlf ltsVk4?{SDWEU2FClm0x`J#K&e~a6DGЦ%#EwZl/_Oaub{=B%?w / cŗu)Rn!@Bn4P3A 'sl8QMhjyp>W} ;@)H,Yx0jߒLȂ"6τF]vP;}z ?Ӎ5ZT̸8%\ɡoZ(NG(?lqޢkKIoӍ** .ZKo;9ām62#y);csϿKF,rp|ο?N8?Ήrl.^ٽb z;Ae}M 'Ѳ 5%+ 6#e.>/j6p#k*W!x%pj8Nɷ?k^裊nこsc"nH^/$G01 jmAO8h[_*9jQPh3vCw-BQϧՎ^v?Qҟe$JmJ^V˲qmFix_'AF-tgHLtP[US 80mV|V\4oƲ'g@ 9G {eϮݫơB'h8lJӸEDQi><ȹYAM:9[OO9U듛 []]vX0-~fsC= 4mC^-;ltOIW:lLjwxlEGOM.[i,_p.f}Qaا x0JI~bHw'ъ~tp1[yF]Wy`^Vd`cg3Sv4!%\Ў(l>ɯ9{N8p5#\xMeA?nNb˄"Ҳq^4`sBPxXE,Tbd;cctc#T9zFZ_&s =aIEλBy{zn58dA+*`KDGL?y1OiCAm8}#+1g-zo0{ZL -5UVR/8[r#ΧmQGO vAO%BAwPj im.;rCV!:͍eVYyԪ&>/\Otw&G0qY{¹UKGKSR흴am~0£v) U.dR 'UmRHqR[QPEvnʜCNTוm (Ҹ3RQ5c ybLkQ\P~5d ic rqT'mHEh_ԝe"1~J?&ir@Ĵ]:!NTnYhl=&t:tH5zkoISE5b%B"<.D,J?}g-RRf=2߅mX%#)=70yc=ZB"ĽHF$XWfɒi< &^sOJ.8^k>N4as?dzj)+Pp(nSM)ߩ'}`WR9sai+J|ojZaŹ,h i_T&/9l1h% ,oKlfk>fG]BK2!,Uk3TEDQ9)6ޝYV^nmP1uQؐh9z:nïe mK! H'b?fٕioL>Z{#M@e -˕s%zMh&Y""*/p(ݘxE|ۈΣ9Q.6`?kY@nΨwG!Rjyd:8"•.量b,@@8IV4ء ƥ$xkDKbOc&Ge<]/߭k9y;N#BQOp"ٖNJ, @Fzgok jHuAq+'鹥* /<D,f!@'t$/k@"Ek' >( ;!2Kos.-蒘qQ8iz` &Xt25Jֱ?hdm07Xg"Q$R'ƥ btNG5h#p1-ϻNa+c(7060Ϭa~(јZ,|ihH"@ a\5. 2!Ry\PG;u{|AR6}E9Q>FHRJ_A~˔|BIJl9⯱!MkQŪX)cU҂XE@:},,v 5o2{9 z:N3;NLLI+R~eq?>V_JH?7F[9ŏ&H/8ɽ7%%R&oQ(C9ƩW>L;48%ao>? YW66b2 b:ez<ݎ ,ܶTu,;;6RҊ90x+?chG#tpThis file krypted Wed Jan 12 18:23:00 2000 i)UyAvf~Ć< :Wd[l[ d_1#_`/*o2I>X#^#ಲqܫ 'pi )"aϣfk9k; "Lɝ QQl}j0ۚOn\S76IߏHВSBm AsTņ>0|Ѯ "+9Cn}g!H#)Ld3f8|9d 7'Z)hs2]M!T,}C)yG0KG ó>%^н-@ c?7k;^Գ$1C.t9ghů$*5 BJW)ak#S{GFث(?, ?#xD~x`v3LiE# 'lBJx4Ee}p@ꦥ}2r)+Tpډ WTϠ^d +Rp~] s'_O˖) ۤ59y%]NvT!Zw$jI,(X h~%h(QC&xd;;l6#&|gřRhGĺ\gJ[5 >3eơ>۲)qշf9WːRͧLfH66< ڇ$k,t `O[u5&桊TU,eT7eg*)X͏"a.9&VA|0 uonk)Mtj CoA2;t5ţ$ E*;N0(g}ˍ!s!K C*oX*N(z̜,+hb͡g a+ynJ1,ut55] Wg\ xQ(+T|%CgV뗰@͐<.(A҄G*RP ci\d6j ”tAJ_S 0'O_ "W{ :Mo" tW%~GHJՕ4;q@PcQYaՉ}e~2;%2bAkK-NwO/7t:-8?pu}p|*n8xKi Wuz-V2#E9 Ф{H\G̳[ugt'jV8[s&ZdG€={lC׷bO"a揉Ɔ 𬊣Rx3 M>\>FL@dޫqjt\Mm!0tXaҰhZF2ܻqrrd_ƞqH}_ƪ 0깩nt 5bt+Wuowф0+=S6N#us $Q9<|,*˩r'9J->Jm= j~^f$^^onphsK. L>wyxnG-n4ӖMV+`  0zƀ QYBVŒ)A7јLa$o-Y6,vNscxbh€V%.=MFs-c]LL5oXdhQJ2] E8[q'in.Dgf8OrF}of\^H)D- /؈N/>u#>r-Mh?o?*~p=sNXj}9%^O#JĄ*Þdp-74-c!SF%A7ᮘ 0iԞyUN= hH_wr!FxY`x_?>ީz 43B s1ީy^6 B Dܲw\%dq Rn_i7EӒ&T|hxQ|aľdc/ fXiǬ-rК:*e:#$'uD-O<JD󆄹]oq^3b~t8 NH}AgUaK%"q0V}ɸQy[|Q.+e1Pߓ~D+)akшǪDj^R/v; Ex]2*92Ǟ>Oe $9΅;BswrrXBuJz2Syߢ7,g<ݭEc. /%뿱hO~]GOو4rWpZ 1ysĒ4[S_dLkA:_KsQɩϦY6# ;%VJϱ[|1!<%{}]p6}46ed'g.1MOlh;J~ $\@8^r 쓆l7 ]b:,5k,=t. }Φrs H9E[cʅJp\+!Zb$2o3w;jɲ}hM]?ys`ExjqL߾׾8,ټe-i :,vC"w S,&lP sZD7#LV7 ȓ =맕80Xa*ܷ)s@TudAUeVNl\p@܊.F)g%#1@?_L;@^--E.an6k?ߗsļ}#xR~)n4vgb"5`{-M ֤c֝k!(d"/q䖅ڡaVOl)&jSОtsd8~ n"{XeYZdrwY>& 3b8odCx+NN̛ t5;:`d(jβgY1(XYD}kϘ͜m2[#2P-Wh2ʏscꟃk5RV/GSM^YIJE_-a1=#c ̬eH V PUef@3wn 2, ZnLbvbT]p؋&F xBn\t-s~~9|wo5M2>u?˅8=8PNӔ0WmMR8UjX̲qL$'5tp;v$=ϯ>ºdMR("] 3j0*٦L=v]X@Y,UWͨw8C&'GhY)z~i<07FE+ӊlbp]PP34BN{ ͗e% ׯHXŨ}2C!omcu>67#)r$.s`n!ʧ{E} !>m;V )qԒjA%~&$4Ro n6ܚcVD;7`%SRi8Z %DDxI S} YD6g”~sh*[4OwS{%h@s?m~N9ЩuJͽͰK%p~ /3x6Cˎ$t١Av'BF+wg-}WEX| oN\ ݨϽKWK`ԎXsEf;OYlqҫi/Q. S; Vy;g,oLyKߤVse=')z!FlA?sNJkZ ;܇eĩ *U~ݷaX&|"=~n&&:*^5\ņ =grG))7RcB23Aft6@faХ^ibc~*>M2XeA|BPk$rlJ9?2rdf;kV5 d JnD2lkx:YZo)C+Sk Ծz5yc> RjLAy3 u0єC@i!ñCNOL泓$$VtX6NGѮg˼;REUPMDuhc]քz+wS 9XT:7p3(NZtv2"hv֛*˥m+H akŔ1UބU1#i%n>ד76B6=FN ΟˢsE]>KS~`DmQۑ v L@8i ⋹\:˻ӺE* O{2x 1 6IW ~fn .tSYvk qf6b+}F |.qFj\Y<*xDmn?'"~``!7\GO3Uᐅ8n7*bNnoSUR+ј`^mocR!_BPՇLB#Ɉ6|3X=B_I쩓멸88GGq|tyPpw!:k֝K֜m# ԵQ),VrGpjj9_I̭mg9|e4h^uR`8LUz\f\4Q! }qn}-IqA`DY`n@+x14aa4 BV=\_zX[9y%'m|o?5Im#P ?Q뙖0aN8 6\qMJW_PM^Ferݍ0w*tәs/ԁE}нjoOǎ"vV5Q[})!\;ٸn4]1o,&Ǹ[vvSRY?5?9%jf٨nwrOd@ *WhKNQApd0",(lj'~x ߒBAƝLF+B#|HSi5ln1K%}4ʝԎ,Έ|JfĹoΉUcsᬗt%:DA^`rFCi$EZ seu.Cfɭ{u&q$w.X\M:؈OqYH.$2)&}"7-7erQ|;zn <_d*.Dp (WxtRkeo&Nparp\Y)hh~_Ym6}bu`T7pDV#m0ZSͻ'Q:?I@UWu7ӆ`U6'rmqn 5Tm AY7tyCQ-7$I›N9Q+R-e#O{%l0`-<4ks=p`3 HUa#6*Z3mZ6{֫89Z8gـǡ4F8DW G ~5WR{`>L1 Nۨz,1;.KslM3 GBm}0m%:Db_J (rPpY,^\k?YN,{#yPEYi/\%ĥ&/fcLyflOuj:Qկ S&Iɦ4lZkn#7;`/6J2S%K%Htd G![?#J״t#cikr*>flٜ`#JeYC0Sנ(DcTEt r$.FǮ<R>/HG뒊;3̔K- #$VZXLvN$>;Kg2B|0lvnyVL Z2;587i32hVS$5]>ٺmn^~ˆDmށK^O:ك!-aUŒF6%yeM IW=QN}ffSSI0.ޤ"A{Zu~Tٴ$Q h!Ww"`X ]ѭwApLR⯐KY( Y2Wmf --|Tޢc?GhZH~kQT{9O`{:Oapl*?pAm&p٢Չ_~x#'ArN\hBabs/ {j f@T , J @~A6ˊ2L5ËSe͈Ev"ϑP^6hvХ'|d[-.V_^`aq}LWW^^?^ܐRlub]R)բ\l);V~A@X\M !S(a28fؘ5+h]6e_0A[ACA,%S*6S:xB>63 cIXxc,vjin$ܢ^3{^6 BŮ<Yi\ /GH nY$ŹjϣJmA':Dz=н$WѢ.\6fE4$^yP恚b'ULhBT4VPAg ̨÷E5{rB(V:fjID}ΐ1 Bf jWXdN BjBzbj_xE0f)һR3ll ~Z 9xpC2d?78bfSA;u$NOueR&s9IyxG%΍9ht ~]z||r}`}06uZ%i/#on2T's]NuC3 Mb`; L~;_$Y$ l EEŃiڻ4 εɔZ61WTµi趾pCCeAZny5 |sE L0sr )xk*iNP12 ((pf_Lzex.UPqDjm*F:22X"U<;MPKyF/ ZR1bܼas-Dſ #޵cGpvyCP!Bnn8NdHzzS#Z]b~('e*}.N:.J{iÌ?:{Ex+Z(;Q7=!XA- BTq9Y9LN@ʣbl3ש`#{.Bw`@uB=kV,!x4 ڱ u'ٍz4YFEwYXtZ~>Om)yV",ZwF1$6ZGl~CJGRMdd[.mn_?˞d-88_4`\*_'1Vo-yx5l}u&CMƋ%'lY, co0ۯ5imc5aꇨ,n_/ L,‚A1 8(%:Nrw(dT?9{ IwFlLsǎ\Oa׵A4jO&TI8dտCn^De]5^T,Zae /]sǚN16K\Z'Paw>2eEB3EJΗh@XӋO49|)zD̟|A?ofFMx聯ԅ0 Aڀ53PBE1*ȪmE٠b^+[4}!?NMӜSd|jp6"|;POz |*39//\k* ䷇PBWKeɝv,yqT##p /"+Z2dF+m!U9h4'|د"3'E YqW-KF9Oʸܫh*YThT7_%/r#UPVL[nAATSb/ԍ1@!'f!5[jt+"AmJkπQ{8;ED1{E%k"aCCpn,B*wg44mʹ")%H7}NG+TO6 -hPY-t7o2Ux]C-ct\ё^_{NQ RC%QRR9t-!Ls,gsfiL1ؕ,$oU-޳DBs ~^ud+TL {wyC$Jk,"%)&R*b3o@4'ml]y6t5IYiLS͹z[aIgLJ1=`'|fsQ &hyn{d*Gnv+B*:lԎ/Z8ɘu!IBvU(ѭJR=W;IAj_@v;j{y?D(yGU3s;JCKBt*.aok #U楲\-i|AIBVYnpS?wT5u 8OJ#}pPa?džD,Ahf~5V\|0Y˳ ͨ@{bE!&;3tźI|SZ80g,:Vdk}V\T@_ (GpA|@ xRO9Lǰ18Pv>WLzF.p &1 bVb$Yό,%PԞ~&/Tח1}|bL i0%qtP]Hf/Wh6]҅kQt %S]KyYB78F߁Μbau&uLC:,m6$ΝNǬ'. $HK2=fū@°_КHyŘaM$ؠ?e]BG˞4NЬ4H)(!? .q4#kHpx\wo&“_; M=(=9i&9SJױ,5ء[8x$ƨO>:ֳ/0n$n+ĢFB8!8?{u!'VRCǣ޵+t[\5Uf':XB/]ӟ&p8zB b"@b>Jzأ uW閂VA\z a6d'!WY«H2;d2뾮OOVf{/h=A6vն]T@9}d. 1^nTI[.kU*٨k*F2,[࣑vUP>(jaTRzEB !WE/L呭cawO.uPLa>oJ8 =Jqhl . f'،RP+7ykjb--aaap@zOvFTy S}&,Wj}ўCYRFwSDt Si<DSB5,H|D꽶G3!$ `5((u U#B|E ":K;H`>r~|kΠg+bYTvެΖI<6;ߑ=,m՟`Ul cNbA2RyP`B}uee{4]Kg}YE$`AvIu6((]da3+J:8$crp>OSPg6IS c-]ܩH3ZG o/! wݳ:\3XPt6' #_͞f?(&b0㇂i\l0]w8xtAmm093#9=9FL&]fM(h!X2NuL?H#T| ϋ~xDS4!-^?,GbAJ@\6"gJ=<'͓4rggHM ijhur! j(G}U ɱ~ֿ[`"S^ 6HNҙyTeU$j{8b8ʼnfzC.6.,.z4{"^:XSxҳtBKc+,1XZJG'f]j"'G OǮ}"|ٰ5[f gxN>+.*|D0S~Ni)GO`VHbGc-CaWNԼ b)ӳZ] 9IJJJw֨CUE~@P\ ц q_m̹8 +?#{AT  i0Pp]K,_