\Question{Fermat's Wristband}
Let $p$ be a prime number and let $k$ be a positive integer.
We have beads of
$k$ different colors, where any two beads of the same color are indistinguishable.
\begin{Parts}
\Part
We place $p$ beads onto a string.
How many different ways are there construct such a sequence of $p$ beads of $k$ different colors?
\Part
How many sequences of $p$ beads on the string have at least two colors?
\Part
Now we tie the two ends of the string together, forming a
wristband.
Two wristbands are equivalent if the sequence of colors on one
can be obtained by rotating the beads on the other.
(For instance, if we have $k=3$ colors, red (R), green (G), and
blue (B), then the length $p = 5$ necklaces RGGBG, GGBGR, GBGRG, BGRGG, and GRGGB are all
equivalent, because these are all rotated versions of each other.)
How many non-equivalent wristbands are there now?
Again, the $p$
beads must not all have the same color.
(Your answer should be a simple function of $k$ and $p$.)
[\textit{Hint}: Think about the fact that rotating all the beads on the wristband to another
position produces an identical wristband.]
\Part Use your answer to part (c) to prove Fermat's little theorem.
\end{Parts}
\Question{Sampling}
Suppose you have balls numbered $1,\dotsc,n$, where $n$ is a positive integer $\ge 2$, inside a coffee mug.
You pick a ball uniformly at random, look at the number on the ball, replace the ball back into the coffee mug, and pick another ball uniformly at random.
\begin{Parts}
\Part What is the probability that the first ball is $1$ and the second ball is $2$?
\Part What is the probability that the second ball's number is strictly less than the first ball's number?
\Part What is the probability that the second ball's number is exactly one greater than the first ball's number?
\Part Now, assume that after you looked at the first ball, you did \textit{not} replace the ball in the coffee mug (instead, you threw the ball away), and then you drew a second ball as before.
Now, what are the answers to the previous parts?
\end{Parts}
\Question{Easter Eggs}
You made the trek to Soda for a Spring Break-themed homework party, and every attendee gets to leave with a party favor. You're given a bag with 20 chocolate eggs and 40 (empty) plastic eggs. You pick 5 eggs without replacement.
\begin{Parts}
\Part What is the probability that the first egg you drew was a chocolate egg?
\nosolspace{1cm}
\Part What is the probability that the second egg you drew was a chocolate egg?
\nosolspace{1cm}
\Part Given that the first egg you drew was an empty plastic one, what is the probability that the fifth egg you drew was also an empty plastic egg?
\nosolspace{1cm}
\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. However, an ace counts as both a low card and a high card, so both $\{A, 2, 3, 4, 5\}$ and $\{10, J, Q, K, A\}$ are considered straights. When drawing a 5 card hand, what is the probability of drawing a straight from a standard 52-card deck?
\Part
What is the probability of drawing a straight or a flush? (A flush is five cards of the same suit.)
\Part
When drawing a 5 card hand, what is the probability of drawing at least one card from each suit?
\Part
Two distinct 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{Balls and Bins, All Day Every Day}
You throw $n$ balls into $n$ bins uniformly at random, where $n$ is a positive 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$?
\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.)
\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.
\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?
\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.)
\end{Parts}