\Question{Combinatorial Proof!} Prove that for $0 < k < n$, $\displaystyle\binom{n}{k} = \sum_{i = 0}^k \binom{n - i - 1}{k - i}$. \Question{Cliques in Random Graphs} In last week's homework you worked on 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. Now consider: % 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{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{Indicator Variables} \begin{Parts} \Part After throwing $n$ balls into $m$ bins at random, what is the expected number of bins that contains exactly $k$ balls? \Part Alice and Bob each draw $k$ cards out of a deck of 52 distinct cards with replacement. Find $k$ such that the expected number of common cards that both Alice and Bob draw is at least $1$. \Part How many people do you need in a room so that you expect that there is going to be a shared birthday on a Monday of the year (assume $52$ Mondays in a year and $365$ days in a year)? \end{Parts} \Question{Poisoned Smarties} Supposed there are 3 men who are all owners of their own Smarties factories. Burr Kelly, being the brightest and most innovative of the men, produces considerably more Smarties than his competitors and has a commanding 45\% of the market share. Yousef See, who inherited his riches, lags behind Burr and produces 35\% of the world's Smarties. Finally Stan Furd, brings up the rear with a measly 20\%. However, a recent string of Smarties related food poisoning has forced the FDA investigate these factories to find the root of the problem. Through his investigations, the inspector found that one Smarty out of every 100 at Kelly's factory was poisonous. At See's factory, 1.5\% of Smarties produced were poisonous. And at Furd's factory, the probability a Smarty was poisonous was 0.02. \begin{Parts} \Part What is the probability that a randomly selected Smarty will be safe to eat? \nosolspace{0.75cm} \Part If we know that a certain Smarty didn't come from Burr Kelly's factory, what is the probability that this Smarty is poisonous? \nosolspace{0.75cm} \Part Given this information, if a randomly selected Smarty is poisonous, what is the probability it came from Stan Furd's Smarties Factory? \nosolspace{0.75cm} \end{Parts} \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