CSTBC Exam 3
Due: August 13, 2007, 11:59pm

This exam is open notes/open lecture and covers 
material from lectures 17-24. You are welcome to use 
any of the course material linked from the CSTBC 
website. You should not use other reference materials. 
Please send me your solutions to the exam via email. If 
you have any questions, please ask me. 

1 Balls in Bins

Suppose that m balls are thrown into n bins uniformly and 
independently at random. In terms of m and n, what is the 
expected number of bins that contain at least one ball?

2 A Hat Game

A group of three people play the following game. Each 
person is blindfolded and given a hat to wear. The hats 
are one of two colors (red or blue), and the colors are 
assigned independently and uniformly at random. Once 
each person is wearing a hat, the blindfolds are 
removed and each person can see the other two hats, but 
is unable to see his/her own hat. Without communicating 
in any way, each person simultaneously writes down one 
of three responses on a sheet of paper: "I guess my hat 
is red", "I guess my hat is blue", or "I choose not to guess"
. 

The group wins if it is the case that no one guesses 
incorrectly and at least one person guesses correctly. 
Describe a way for the group to play the game so that 
they win with probability 3/4. (The group is allowed to 
discuss their strategy before the game begins, but once 
the game begins, no communication is allowed.) 

3 Interviewing Candidates

A manager at a software company must hire a new 
programmer. The manager has the resumes of n people who 
applied for the job and schedules interviews as 
follows. First, the manager shuffles all the resumes so 
that they are in a random order. Next, the manager 
looks at each resume in order and schedules an 
interview whenever the current applicant's resume is 
superior to all previous resumes. What is the expected 
number of interviews that the manager schedules?

4 A Random Walk

In Lecture 23, we introduce the concept of a random 
walk on a line of n spaces. In that case, the token 
moves to the left with probability 1/2 and to the right 
with probability 1/2. Suppose instead that the token moves 
to the left with probability 1/3 and to the right with 
probability 2/3. Now what is the probability that we win 
(i.e. the token falls off of the right hand side)?

5 More Pirates

In Exam 2, we had the following problem: "After 
distributing their treasure, our n pirates from Exam 1 
have worked up an appetite. The pirate ship's cafeteria 
offers three different, non-overlapping dinner times. 
As the strongest pirate, you are in charge of assigning 
each pirate to one of the three dinner slots. 
Unfortunately, not all pirates get along with each 
other. You have a list of k pairs of pirates that have 
fought each other in the past. Prove that you can 
assign pirates to dinners so that at most k/3 of the 
troublesome pairs eat dinner at the same time." 

Suppose that n is divisible by three and that the ship's 
cafeteria has limited seating, so that each dinner can 
accommodate only n/3 pirates. Prove that even with this 
added restriction, you can assign the pirates to dinner 
slots so that at most k/3 troublesome pairs eat dinner at 
the same time. [Hint: although an inductive proof is 
possible, the probabilistic method (see Lecture 24) is easier.]