CS 70 Discrete Mathematics and Probability TheoryFall 2011 Rao HW 6Due Friday, October 7, 5:00pmYou must write up the solution set entirely on your own. You must never look at any other students’ solutions(not even a draft), nor share your own solutions (not even a draft).Please put your answer to each problem on its own sheet of paper, and paper-clip (don’t staple!) the sheetsof paper together. Label each sheet of paper with your name, your discussion section number (101–108),your login, and “CS70–Fall 2011”. Turn in your homework and problem x into the box labeled “CS70 –Fall 2011, Problem x” whereon the 2nd floor of Soda Hall. Failure to follow these instructions will likelycause you to receive no credit at all.1. (32 pts.) This problem counts more than the restThe only way to learn counting is to practice, practice, practice, so here is your chance to do so. Youshould leave your answers as (tidy) expressions involving factorials, binomial coefficients, etc., rather thanevaluating them as decimal numbers (though you are welcome to perform this last step as well for your owninterest if you like, provided it is clearly separated from your main answer). Also, you should explain clearlyhow you arrived at your answers; solutions provided without appropriate explanation will receive no credit.1. How many 13-bit strings are there that contain exactly 5 ones?2. How many 55-bit strings are there that contain more ones than zeros?3. How many different 13-card bridge hands are there? (A bridge hand is obtained by selecting 13 cardsfrom a standard 52-card deck. The order of the cards within a bridge hand is considered irrelevant.)4. How many different 13-card bridge hands contain no aces? [Recall that there are four aces in a standard52-card deck]5. How many different 13-card bridge hands contain all four aces?6. How many different 13-card bridge hands contain exactly 5 spades? [Recall that there are 13 spadesin a standard 52-card deck]7. How many ways are there to order a standard 52-card deck?8. Two identical decks of 52 distinct cards are mixed together, yielding a stack of 104 cards. How manydifferent ways are there to order this stack of 104 cards?9. How many different anagrams of “KENTUCKY" are there? (An anagram of “KENTUCKY" is anyre-ordering of the letters of “KENTUCKY"; i.e., any string made up of the eight letters K, E, N, T, U,C, K, and Y, in any order. The anagram does not have to be an English word.)10. How many different anagrams of “ALASKA" are there?11. How many different anagrams of “MINNESOTA" are there?12. How many different anagrams of “MISSISSIPPI" are there?13. Suppose you are given 8 distinguishable balls (numbered 1 through 8) and 24 bins. How many differentways are there to distribute these 8 balls among these 24 bins?CS 70, Fall 2011, HW 6 114. Suppose you are given 8 indistinguishable balls and 24 bins. How many distinguishable ways are thereto distribute these 8 balls among these 24 bins?15. Suppose you are given 8 indistinguishable balls and 5 bins. How many distinguishable ways are thereto distribute these 8 balls among these 5 bins such that no bin is empty?16. There are 30 students currently enrolled in a class. How many different ways are there to pair up the30 students (that is, to split the class into groups of 2 students)?2. (16 pts.) I’ve got another riddle for youYou have been hired as an actuary by a candy store, and have just been informed that an eccentric millionairehas distributed ten golden tickets to his newly re-opened chocolate factory among the 100 candy bars in yourstore (so there are 90 bars with no tickets, and 10 bars with one ticket each). Given that the store has twentycustomers, each of whom will purchase five candy bars uniformly at random, calculate the probabilities forany particular customer of:1. not receiving any tickets to the chocolate factory2. receiving exactly one ticket to the chocolate factory3. receiving at least one ticket to the chocolate factory3. (20 pts.) Fermat’s necklaceIn the following, let p be a prime number and let k be a positive integer.1. We have an endless supply of beads. The beads come in k different colors. All beads of the same colorare indistinguishable. We have a piece of string. We want to make a pretty decoration by threading pmany beads onto the string (from left to right). We can choose any sequence of colors, subject only toone rule: the p beads must not all have the same color.How many different ways are there construct such a sequence of beads?(Your answer should be a simple function of k and p.)2. Now we tie the two ends of the string together, forming a circular necklace. This lets us freely rotatethe beads around the necklace. We’ll consider two necklaces equivalent if the sequence of colors onone 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 cyclic shifts of each other.)Count how many non-equivalent necklaces there are, if the p beads must not all have the same color.Again, your answer should be a simple function of k and p.[Hint: What can you conclude if rotating all the beads on a necklace to another position produces anidentical looking necklace?]3. How can you use the above to prove Fermat’s little theorem? (Recall that Fermat’s little theorem saysthat if p is prime and a 6≡ 0 (mod p), then ap−1≡ 1 (mod p).)4. (22 pts.) A good bet?Your friend proposes the following game: Each round, she will roll six fair dice. If exactly four distinctnumbers show up, then she will pay you a dollar. Otherwise, you will pay her a dollar. The game will goon for a thousand rounds. Would you be willing to play this game? Justify your answer with a calculation.[HINT: Be very careful in counting the number of ways that exactly four distinct numbers can show up! Youshould find that the game is rather finely balanced!]CS 70, Fall 2011, HW 6
View Full Document
Unlocking...