There are [math]n[/math] applicants for the director of computing. The applicants are interviewed independently by each member of the three-person search committee and ranked from 1 to [math]n[/math]. A candidate will be hired if he or she is ranked first by at least two of the three interviewers. Find the probability that a candidate will be accepted if the members of the committee really have no ability at all to judge the candidates and just rank the candidates randomly. In particular, compare this probability for the case of three candidates and the case of ten candidates.

A symphony orchestra has in its repertoire 30 Haydn symphonies, 15 modern works, and 9 Beethoven symphonies. Its program always consists of a Haydn symphony followed by a modern work, and then a Beethoven symphony.

• How many different programs can it play?
• How many different programs are there if the three pieces can be played in any order?
• How many different three-piece programs are there if more than one piece from the same category can be played and they can be played in any order?

A certain state has license plates showing three numbers and three letters. How many different license plates are possible

• if the numbers must come before the letters?
• if there is no restriction on where the letters and numbers appear?

The door on the computer center has a lock which has five buttons numbered from 1 to 5. The combination of numbers that opens the lock is a sequence of five numbers and is reset every week.

• How many combinations are possible if every button must be used once?
• Assume that the lock can also have combinations that require you to push two buttons simultaneously and then the other three one at a time. How many more combinations does this permit?

A computing center has 3 processors that receive [math]n[/math] jobs, with the jobs assigned to the processors purely at random so that all of the [math]3^n[/math] possible assignments are equally likely. Find the probability that exactly one processor has no jobs.

Prove that at least two people in Atlanta, Georgia, have the same initials, assuming no one has more than four initials.

Find a formula for the probability that among a set of [math]n[/math]people, at least two have their birthdays in the same month of the year (assuming the months are equally likely for birthdays).

Consider the problem of finding the probability of more than one coincidence of birthdays in a group of [math]n[/math] people. These include, for example, three people with the same birthday, or two pairs of people with the same birthday, or larger coincidences. Show how you could compute this probability, and write a computer program to carry out this computation. Use your program to find the smallest number of people for which it would be a favorable bet that there would be more than one coincidence of birthdays.

Suppose that on planet Zorg a year has [math]n[/math] days, and that the lifeforms there are equally likely to have hatched on any day of the year. We would like to estimate [math]d[/math], which is the minimum number of lifeforms needed so that the probability of at least two sharing a birthday exceeds 1/2.

• In Example, it was shown that in a set of [math]d[/math] lifeforms, the probability that no two life forms share a birthday is
  [[math]] {{(n)_d}\over{n^d}}\ , [[/math]]
  where [math](n)_d = (n)(n-1)\cdots (n-d+1)[/math]. Thus, we would like to set this equal to 1/2 and solve for [math]d[/math].
• Using Stirling's Formula, show that
  [[math]] {{(n)_d}\over{n^d}} \sim \biggl(1 + {d\over{n-d}}\biggr)^{n-d + 1/2} e^{-d}\ . [[/math]]
• Now take the logarithm of the right-hand expression, and use the fact that for small values of [math]x[/math], we have
  [[math]] \log(1+x) \sim x - {{x^2}\over 2}\ . [[/math]]
  (We are implicitly using the fact that [math]d[/math] is of smaller order of magnitude than [math]n[/math]. We will also use this fact in part (d).)
• Set the expression found in part (c) equal to [math]-\log(2)[/math], and solve for [math]d[/math] as a function of [math]n[/math], thereby showing that
  [[math]] d \sim \sqrt{2(\log 2)\,n}\ . [[/math]]
  Hint: If all three summands in the expression found in part (b) are used, one obtains a cubic equation in [math]d[/math]. If the smallest of the three terms is thrown away, one obtains a quadratic equation in [math]d[/math].
• Use a computer to calculate the exact values of [math]d[/math] for various values of [math]n[/math]. Compare these values with the approximate values obtained by using the answer to part d).

At a mathematical conference, ten participants are randomly seated around a circular table for meals. Using simulation, estimate the probability that no two people sit next to each other at both lunch and dinner. Can you make an intelligent conjecture for the case of [math]n[/math] participants when [math]n[/math] is large?