Discrete Mathematics and Probability Theory HOMEWORK 8

CS 70 Discrete Mathematics and Probability Theory

HOMEWORK 8
Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of homework party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for
your "Sundry" grade.
Please copy the following statement and sign next to it:
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up.
1 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.
(a) We place p beads onto a string. How many different ways are there construct such a sequence
of p beads of k different colors?
(b) How many sequences of p beads on the string have at least two colors?
(c) 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.)
CS 70, Fall 2017, Homework 8 1
[Hint: Think about the fact that rotating all the beads on the wristband to another position
produces an identical wristband.]
(d) Use your answer to part (c) to prove Fermat’s little theorem.
2 Sampling
Suppose you have balls numbered 1,...,n, where n is a positive integer ≥ 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.
(a) What is the probability that the first ball is 1 and the second ball is 2?
(b) What is the probability that the second ball’s number is strictly less than the first ball’s number?
(c) What is the probability that the second ball’s number is exactly one greater than the first ball’s
number?
(d) Now, assume that after you looked at the first ball, you did 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?
3 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.
(a) What is the probability that the first egg you drew was a chocolate egg?
(b) What is the probability that the second egg you drew was a chocolate egg?
(c) 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?
4 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.
(a) On any given day, what is the probability that you park next to Professor Rao, who is working
there for the summer?
CS 70, Fall 2017, Homework 8 2
(b) What is the probability that there are exactly three cars between yours and Professor Rao’s?
(c) 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?
5 Calculate These... or Else
(a) 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?
(b) What is the probability of drawing a straight or a flush? (A flush is five cards of the same suit.)
(c) When drawing a 5 card hand, what is the probability of drawing at least one card from each
suit?
(d) Two distinct squares are chosen at random on 8 × 8 chessboard. What is the probability that
they share a side?
(e) 8 rooks are placed randomly on an 8×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.)
6 Balls and Bins, All Day Every Day
You throw n balls into n bins uniformly at random, where n is a positive even integer.
(a) What is the probability that exactly k balls land in the first bin, where k is an integer 0 ≤ k ≤ n?
(b) 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.)
(c) 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.
(d) 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?
(e) 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.)
CS 70, Fall 2017, Homework 8 3