Massachusetts Institute of Technology Handout 6 Mathematics for Computer Science August 10, 2004 Professor Charles E. Leiserson

Optional Homework 2

Problem 1. You have a hat in which there are three coins, identical except for color. One coin is gold on both sides, one coin is silver on both sides, and one coin is gold on one side and silver on the other. You withdraw one coin, look at one side, and see that it is gold. What is the probability that the other side is gold?

Problem 2. A bag contains either a black marble or a white marble, each with 50% probability. A white marble is added to the bag, the bag is shaken, and one of the two marbles in the bag is removed. The removed marble proves to be white. What is the probability that the marble remaining in the bag is also white?

Problem 3. A box contains two seemingly identical coins. One is fair (the probability of heads is 1/2), but the other is biased with a 2/3 probability of heads. One of the coins is tossed once, resulting in heads. The other is tossed three times, resulting in two heads and one tail. Which coin is more likely to be the biased one?

Problem 4. (Hard.) An ordinary deck of 52 cards is shuffled randomly and placed face down on the table. The cards are turned over one at a time. Before each card is turned over, you are given the opportunity to say “now.” When you say “now,” if the next card turned over is black, you win. If it is red, or if you go through the whole deck without saying “now,” you lose.

The strategy of saying “now” before the very first card is turned over obviously gives you a 50-50 chance of winning. Is there a better strategy, one that allows you to win more than half the time? What is the probability of winning with the best strategy?

Problem 5. (Hard.) Someone writes two different real numbers on two cards and places them face down on the table. Your goal is to choose the card with the larger number. Obviously, you can win at this game half the time by randomly choosing one of the cards. But, suppose that you are given the chance to turn over either one of the cards and look at the number on it before choosing which card has the larger number. Is there a strategy for winning more than half the time?