Massachusetts Institute of Technology Handout 6 Pre-Algorithms Minicourse July 31, 2001 Charles E. Leiserson

Optional Homework 2

Problem 1. 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 2. (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?