University of California, Berkeley - CS 70 HW08SOLN. CS 70 Discrete Mathematics and Probability Theory. Homework Solution 8. 100%.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Fall 2017 Kannan Ramchandran and Satish Rao 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. 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. (signature here) 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.) [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? (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. f8;9;10;J;Qg is a straight. Values do not loop around, so fQ;K;A;2;3g is not a straight. However, an ace counts as both a low card and a high card, so both fA;2;3;4;5g and f10;J;Q;K;Ag 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.) [Show More]

Last updated: 2 years ago

Preview 1 out of 7 pages