Massachusetts Institute of Technology Handout 7 Mathematics for Computer Science August 8, 2002 Prof. Charles E. Leiserson

Optional Homework 3

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. The following problem appeared last Sunday in the “Ask Marilyn” column of Parade magazine:

Suppose you’re on a game show. There are four boxes in an L-shaped configuration like this:

# 1 # 2 # 3 # 4

The host tells you: 1) One of the vertical boxes contains a chicken; and 2) one of the horizontal boxes contains a chicken. What are the chances that a chicken is in the corner box? In one way, the chances seem to be 1 in 3; but in another way, the chances seem to be 1 in 2. They can’t both be right! —Toby Click, Macon, Ga.

What’s the answer, readers? Send your reply to marilyn@parade.com. Also, answer this: Which box is most likely to contain a chicken? We’ll publish the first letter that correctly answers both questions.

What are the answers? What strategy gives you the best chance of picking a box containing a chicken?

Problem 3. 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 4. (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?