\Question{Cliques in Random Graphs} Consider a graph $G = (V,E)$ on $n$ vertices which is generated by the following random process: for each pair of vertices $u$ and $v$, we flip a fair coin and place an (undirected) edge between $u$ and $v$ if and only if the coin comes up heads. So for example if $n = 2$, then with probability $1/2$, $G = (V,E)$ is the graph consisting of two vertices connected by an edge, and with probability $1/2$ it is the graph consisting of two isolated vertices. \begin{Parts} \Part What is the size of the sample space? \Part A $k$-clique in graph is a set of $k$ vertices which are pairwise adjacent (every pair of vertices is connected by an edge). For example a $3$-clique is a triangle. What is the probability that a particular set of $k$ vertices forms a $k$-clique? \Part Prove that ${n \choose k} \le n^k$. \textit{Optional:} Can you come up with a combinatorial proof? Of course, an algebraic proof would also get full credit. \Part Prove that the probability that the graph contains a $k$-clique, for $k \geq 4{\log n}+1$, is at most $1/n$. (The log is taken base 2). \textit{Hint:} Apply the union bound and part (c). \end{Parts} \Question{Identity Theft} A group of $n$ friends go to the gym together, and while they are playing basketball, they leave their bags against the nearby wall. An evildoer comes, takes the student ID cards from the bags, randomly rearranges them, and places them back in the bags, one ID card per bag. \begin{Parts} \Part What is the probability that no one receives his or her own ID card back? \textit{Hint}: Use the inclusion-exclusion principle. \Part What is the limit of this proability as $n \to \infty$? \textit{Hint:} $\e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$. \end{Parts} \Question{Balls and Bins, All Day Every Day} You throw $n$ balls into $n$ bins uniformly at random, where $n$ is a positive \emph{even} integer. \begin{Parts} \Part What is the probability that exactly $k$ balls land in the first bin, where $k$ is an integer $0 \le k \le n$? \nosolspace{1.5cm} \Part What is the probability $p$ that at least half of the balls land in the first bin? (You may leave your answer as a summation.) \nosolspace{1.5cm} \Part Using the union bound, give a simple upper bound, in terms of $p$, on the probability that some bin contains at least half of the balls. \nosolspace{1.5cm} \Part What is the probability, in terms of $p$, that at least half of the balls land in the first bin, or at least half of the balls land in the second bin? \nosolspace{1.5cm} \Part After you throw the balls into the bins, you walk over to the bin which contains the first ball you threw, and you randomly pick a ball from this bin. What is the probability that you pick up the first ball you threw? (Again, leave your answer as a summation.) \nosolspace{1.5cm} \end{Parts} \Question{Babak's Dice} Professor Ayazifar rolls three fair six-sided dice. \begin{enumerate}[(a)] \item Let $X$ denote the maximum of the three values rolled. What is the distribution of $X$ (that is, $\Pr[ X = x ]$ for $x =1, 2, 3,4,6$)? You can leave your final answer in terms of "x". [\textit{Hint}: Try to first compute $\Pr[X \le x]$ for $x =1, 2,3,4,5,6]$. \item Let $Y$ denote the minimum of the three values rolled. What is the distribution of $Y$? \end{enumerate} \Question{Testing Model Planes} Dennis is testing model airplanes. He starts with $n$ model planes which each independently have probability $p$ of flying successfully each time they are flown, where \$0