CS 70 Discrete Mathematics and Probability Theory Fall 2017 Kannan Ramchandran and Satish Rao HOMEWORK 8 University of California, Berkeley - CS 70HW08SOLN ALL SOLUTIONS CORRECT

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. CS 70, Fall 2017, Homework 8 [Show More]

Last updated: 1 year ago

Preview 1 out of 8 pages