\Question{Story Problems}
\newcommand{\sblank}{\vspace{1in}}
Prove the following identities by combinatorial argument:
\begin{Parts}
%\Part $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
\Part $\binom{2n}{2} = 2 \binom{n}{2} + n^2$
\Part $n^2 = 2 \binom{n}{2} + n$
\Part $\sum_{k=0}^n k {n \choose k} = n2^{n-1}$ \\
\textit{Hint:} Consider how many ways there are to pick groups of people ("teams") and then a representative ("team leaders").
\Part $\sum_{k=j}^n {n \choose k} {k \choose j} = 2^{n-j} {n \choose j}$ \\
\textit{Hint:} Consider a generalization of the previous part.
\end{Parts}
% Carries over from 10M
\Question{Probability Potpourri}
Prove a brief justification for each part.
\begin{Parts}
\Part For two events $A$ and $B$ in any probability space, show that $\Pr(A \setminus B) \geq \Pr(A) - \Pr(B)$.
\Part If $|\Omega| = n$, how many distinct events does the probability space have?
\Part Find some probability space $\Omega$ and three events $A, B$, and $C \subseteq \Omega$ such that $\Pr(A) > \Pr(B)$ and $\Pr(A \mid C) < \Pr(B \mid C)$.
\Part If two events $C$ and $D$ are disjoint and $\Pr(C) > 0$ and $\Pr(D) > 0$, can $C$ and $D$ be independent? If so, provide an example. If not, why not?
\Part Suppose $\Pr(D \mid C) = \Pr(D \mid \overline{C})$, where $\overline{C}$ is the complement of $C$. Prove that $D$ is independent of $C$.
\end{Parts}
\Question{Parking Lots}
Some of the CS 70 staff members founded a start-up company, and you just got hired.
The company has twelve employees (including yourself), each of whom drive a car to work,
and twelve parking spaces arranged in a row. You may assume that each day all orderings
of the twelve cars are equally likely.
\begin{Parts}
\Part On any given day, what is the probability that you park next to Professor Rao,
who is working there for the summer?
\Part What is the probability that there are exactly three cars between yours
and Professor Rao's?
\Part Suppose that, on some given day, you park in a space that is not at one of
the ends of the row. As you leave your office, you know that exactly five of
your colleagues have left work before you. Assuming that you remember nothing
about where these colleagues had parked, what is the probability that you will
find both spaces on either side of your car unoccupied?
\end{Parts}
\Question{Calculate These... or Else}
\begin{Parts}
\Part
A straight is defined as a 5 card hand such that the card values can be arranged in consecutive ascending order, i.e.\ $\{8,9,10,J,Q\}$ is a straight. Values do not loop around, so $\{Q, K, A, 2, 3\}$ is not a straight. When drawing a 5 card hand, what is the probability of drawing a straight from a standard 52-card deck?
\Part
When drawing a 5 card hand, what is the probability of drawing at least one card from each suit?
\Part
Two squares are chosen at random on $8\times 8$ chessboard. What is the probability that they share a side?
\Part
8 rooks are placed randomly on an $8\times 8$ chessboard. What is the probability none of them are attacking each other? (Two rooks attack each other if they are in the same row, or in the same column).
\Part A bag has two quarters and a penny. If someone removes a coin, the Coin-Replenisher will come and drop in 1 of the coin that was just removed with $3/4$ probability and with $1/4$ probability drop in 1 of the opposite coin. Someone removes one of the coins at random. The Coin-Replenisher drops in a penny. You randomly take a coin from the bag. What is the probability you take a quarter?
\end{Parts}
\Question{Independent Complements}
Let $\Omega$ be a sample space, and let $A,B \subseteq \Omega$ be two independent events.
\begin{Parts}
\Part Prove or disprove: $\overline{A}$ and $\overline{B}$ are necessarily independent.
\Part Prove or disprove: $A$ and $\overline{B}$ are necessarily independent.
\Part Prove or disprove: $A$ and $\overline{A}$ are necessarily independent.
\Part Prove or disprove: It is possible that $A=B$.
\end{Parts}
\Question{Bag of Coins}
Your friend Forest has a bag of $n$ coins. You know that $k$ are biased with
probability $p$ (i.e.\ these coins have probability $p$ of being heads). Let
$F$ be the event that Forest picks a fair coin, and let $B$ be the event that
Forest picks a biased coin. Forest draws three coins from the bag, but he does
not know which are biased and which are fair.
\begin{Parts}
\Part What is the probability of $FFB$?
\Part What is the probability that the third coin he draws is biased?
\Part What is the probability of picking at least two fair coins?
\Part Given that Forest flips the second coin and sees heads, what is the
probability that this coin is biased?
\end{Parts}