CS 70 Discrete Mathematics for CS Spring 2004 Papadimitriou/Vazirani HW 8

Due on Friday, March 19 at 5:00PM

1. (10 pts.) Any comments?

Are you comfortable with the mixture of intuition and formalism in the explanation of discrete probability? Any other comments on the lectures? Are discussion sections too fast, too slow, or just right? Any comments about what we could have done better in the past week would be appreciated.

Please staple your homework before submitting it.

2. (20 pts.) Elementary counting/Probability

(a) Eight students are traveling home from college in Berkeley to their homes in Los Angeles. Among them they have two cars, each of which will hold five passengers. How many ways can they distribute themselves in the two cars?

(b) Compute the probability that in a class of five students at least two have adjacent or identical birthdays.

(c) Although Robin Hood is an excellent archer, getting a “bullseye” nine times out of ten, he is facing stiff opposition in the tournament. To win he must get at least four bullseyes with the next five arrows. However, if he gets five bullseyes, he runs the risk of exposing his identity to the sheriff. Assume that if he wants to miss the bullseye he can do so with certainty. What is the probability that Robin wins the tournament?

3. (15 pts.) Mom vs. Girlfriend Every evening a man either visits his mother, who lives downtown, or visits his girlfriend, who lives uptown. In order to be completely fair, he goes to the bus stop every evening at a random time and takes either the uptown or the downtown bus, whichever comes first. As it happens each of the two kinds of buses stop at the bus stop every 15 minutes with perfect regularity (according to a fixed schedule). Yet he visits his mother only around twice each month. How come?

4. (15 pts.) Combinatorial proof Give a combinatorial proof of the following identity:

n2^{n−1} = \binom{n}{1} + 2\binom{n}{2} + ··· (n − 1)\binom{n}{n − 1} + n\binom{n}{n} .

5. (20 pts.) Monty Hall

(a) After many years, the standard version of the game with three doors becomes a little boring, so Monty decides to increase the number of doors to four (with one prize and three goats). What is now the probability that the contestant wins under the switching strategy?

(b) Consider the following variant of the Monty Hall problem. The contestant picks a door, but instead of revealing this door to Monty, he/she writes it down on a piece of paper. Monty then opens one of the two goat doors (chosen uniformly at random). If the door opened by Monty is the one chosen by the contestant, then the contestant knows he was wrong and picks one of the remaining two doors at random. Otherwise (i.e., when the door opened by Monty is not his chosen door) the contestant is given the option of switching to the other unopened door. (Note that the switching option comes into play only in this second case.) Should the contestant switch? First answer this question using probabilistic reasoning. Then write down (in tree form) the entire sample space for this version of the game, and compute the probability that the contestant wins under both the switching and sticking stategies.

6. (20 pts.) Union Bound Prove that the probability of getting a run of 2logn H′s in a row when a fair coin is flipped n times is at most 1/n.

7. (20 pts.) Dice (Extra-Credit) Show how to label the sides of three six-sided dice A, B, and C so that

(a) when you roll dice A and B, the number that comes up on die A is on average larger than the number that comes up on die B

(b) when you roll dice B and C, the number that comes up on die B is on average larger than the number that comes up on die C

(c) when you roll dice C and A, the number that comes up on die C is on average larger than the number that comes up on die A.

The labels on the sides of any one die do not have to be distinct. Compute the probability that the number that comes up on die A is larger than the number that comes up on die B for the dice you construct, and repeat this calculation for the pair B and C and the pair C and A (by the definition of “on average,” each of these three probabilities should be at least 1/2.)