CS 237, Fall 2007

Date Due: Thursday, November 29

Reading: Chapter 6, pages 106-112.

Problems:

1. Page 119, problem 5.4 2. Page 120, problem 5.7 part a. and b.

3. A hat contains n balls, each with a different number on it. In each turn, a ball is drawn uniformly at random and without replacement, and shown to you. At some point when you see a ball drawn you say, "Stop, that is the largest numbered ball." If you are able to identify the ball with the largest number when it is drawn, you win the game, otherwise you loose.

Give a scheme that wins with probability at least 1/4.

4. Consider throwing n balls into n bins where each ball is thrown independently and uniformly at random into a bin.

i. What is the probability that a given bin (say the first bin) contains exactly 3 balls?

ii. What is the probability that exactly 3 bins contain exactly 1 ball, and all the others contains 0 or more than 1 ?