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

Due on Wednesday, March 17 at 11:59PM

1. (10 pts.) Any comments? What’s the one thing you’d most like to see explained better in lecture or discussion sections? Are lectures too fast, too slow, or just right? 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.) Pistol Duel A certain theory TA—call him Michael—wants to go out with the stunningly beautiful hostess of College Avenue’s premiere Italian restuarant, Trattoria La Siciliana. Unfortunately, after asking her out, he learns that she’s already going out with one of her coworkers, a waiter who has an uncanny resemblance to Lance of the now-defunct N*Sync, the greatest musical force of fin de siècle America. Eerily, it turns out that the waiter’s name is in fact Lance.

Inspired by late-night reruns of Celebrity Deathmatch, Michael challenges Lance to a pistol duel at sunset—the survivor will then takeover (or continue) boyfriend duties.

Suppose Michael shoots with 75% accuracy (i.e., 3/4 of his shots send his target into the afterlife) and Lance shoots with 80% accuracy. The duel will consist of Michael and Lance taking turns attempting to shoot the other until one of them goes “Bye Bye Bye.”

(a) Suppose Michael gets to shoot first. What is the probability that Michael wins the duel? What is the probability that Lance wins the duel?

(b) Suppose Lance gets to shoot first. What is the probability that Michael wins the duel? What is the probability that Lance wins the duel?

(c) More generally, suppose that Michael always shoots first and his target with probability p_{1} and that Lance hits his target with probbility p_{2}, 0 ≤ p_{1},p_{2} ≤ 1. (Note that p_{1} and p_{2} are not necessarily distinct.) Compute the probability of victory for each of the players.

3. (20 pts.) Pistol Duel Redux Three theory TAs, call them Hoeteck, Michael, and Jordan, are the last to arrive at Theory Lunch one week. Luckily, there are three panini sandwiches left, but unluckily, two are eggplant sandwiches and only one a chicken sandwich.

Since all three want the chicken sandwich, they decide to resolve their dispute by a pistol duel at high noon (i.e., immediately) in the Wozniak Lounge. Suppose Hoeteck shoots with 50% accuracy, Michael with 75% accuracy, and Jordan with 100% accuracy. The duel will consist of the three taking shots (of their choosing) in a specified order—Hoeteck will shoot first, then Michael, and finally Jordan—until only one is left standing. Suppose that each player is infinitely skilled in discrete probability calculations, so each knows what his “perfect strategy” is.

(a) To maximize his probability of survival, where should Hoeteck shoot first? (Hint: The TAs can choose to shoot into the air, in which case they definitely do not hit the other TAs.)

(b) Compute the probabilities of victory for each of the three TAs.

(c) Suppose Michael got to shoot first in his duel with Lance. What is the probability that he gets both the girl and the chicken sandwich (what a great week that would be!)?

4. (20 pts.) Palindromes

(a) How many even numbers in [100,999] have distinct digits?

(b) How many palindromes (numbers that are the same when you write them backwards) are in this range?

(c) How about the range [1000,9999]?

(Note: You may not brute force this one by writing a program—show your work!)

5. (30 pts.) Monty Hall

(a) 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.) 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. Should the contestant switch?

(b) 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?

(c) Finally, suppose there are n doors and m ≤ n − 2 prizes (each one behind a different color). Again, the contestant picks a door and Monty then opens a goat door. (The condition m ≤ n − 2 ensures that this is always possible.) What is the probability of winning under the “sticking” strategy? What is the probability of winning under the “switching” strategy? Both of your answers should be given as a function of m and n.

6. (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.)