\documentclass[12pt]{article} \usepackage{comment} \usepackage{amsmath} \usepackage{amssymb} % for \nmid \begin{document} \centerline{\bf Midterm Two, April 20 8:00PM-10:15PM on Zoom} \newcommand{\MOD}{{\rm MOD}} \newcommand{\PRIMES}{{\rm PRIMES}} \newcommand{\NSQ}{{\rm NSQ}} \newcommand{\into}{{\rightarrow}} \newcommand{\lf}{\left\lfloor} \newcommand{\rf}{\right\rfloor} \newcommand{\lc}{\left\lceil} \newcommand{\rc}{\right\rceil} \newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\Z}{{\sf Z}} \newcommand{\N}{{\sf N}} \newcommand{\Q}{{\sf Q}} \newcommand{\R}{{\sf R}} \newcommand{\Rpos}{{\sf R}^+} \centerline{\bf WARNING: THIS MID IS THREE PAGES LONG!!!!!!!!!!!!!!!!!} \begin{enumerate} \item (15 points) \begin{enumerate} \item (5 points) What is the coefficient of $x^2y^3z^4$ in $$(x+y+z)^9$$ \item (10 points) What is the coefficient of $x^ay^bz^c$ in $$(x+y+z)^{a+b+c}$$ \end{enumerate} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (20 points--5 points each) The Narns play card games with a cards that have ranks in the set $\{1,2,\ldots,r\}$ and suites in the set $\{1,\ldots,s\}$. In Narn Poker, each player gets $h$ cards. We assume that both $r$ and $s$ are squares, so $\sqrt{r}$ and $\sqrt{s}$ are natural numbers. \begin{enumerate} \item A {\it Square Hand} is a hand where all of the cards have square rank. What is the probability of getting a Square Hand? (Its okay if they are of the same suite, or not.) \item A {\it Square Flush} is a hand where all of the cards have a square rank and all of the suites are the same. What is the probability of getting a Square Flush? \item An {\it Apple} is when you get two of the same rank. There are no other restrictions, so for example, if you had 3 of the same rank, that would still be an Apple. What is the probability of getting an Apple. \end{enumerate} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (15 points) In this problem we guide you through the birthday paradox with $m$ balls in $n$ boxes where we want the probability that at least $k$ balls go in the same box is $\ge \frac{1}{2}$. (HINT: Follow the proof for THREE balls in a box and feel free to use the approximations I use there.) Assume that $m$ is much less than $n$. Assume that $k$ is much less than both $n,m$. We put $m$ balls into $n$ boxes at random. \begin{enumerate} \item Let $i_1,\ldots,i_k$ be $k$ balls. What is the probability they are all in the same box? \item What is the (approx) probability that NO set of $k$ is in the same box? (Use three approximations here: (a) that the events are independent, and (b) use $(1-x)$ is approximately $e^{-x}$, and (c) $\binom{m}{k}\sim \frac{m^k}{k!}$. \item Think of $n,k$ as being fixed but $m$ as being varrying. Approximatly how large does $m$ have to be so that the prob that $k$ are in the same box is $\ge \frac{1}{2}$? \end{enumerate} \end{enumerate} \end{document}