\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}

\begin{document}
\psol{9}{April 27, 1999}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\bigskip \noindent {\bf Solution:} #1}

\reading{Sections 4.3 and 4.6 in Rosen.  Fall 97 lecture notes 15, 16,
18, and 19.}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Solve the following counting problems.
Please leave factorials and binomial coefficients in your answers rather
than evaluate them.

\begin{problemparts}

\problempart How many poker hands contain no diamonds?

\solution{
\[
\binom{39}{5}
\]
}

\problempart How many different ways are there to arrange the letters
in the word BOOKKEEPER?

\solution{
\[
\frac{10!}{2! \ 2! \ 3!}
\]
}

\problempart A bug starts at position $(0, 0)$ and wants to reach
position $(4, 6)$ in 10 steps.  Each step is either north, south,
east, or west; that is, each step either increments or decrements one
coordinate.  How many different paths can the bug choose from?

\solution{
\[
\binom{10}{4}
\]
}

\problempart How many poker hands have cards with consecutive values?
(The possible values of a card, from lowest to highest, are $2, 3, 4,
\ldots, 10, J, Q, K, A$.)

\solution{There are 9 ways to choose the lowest value, and $4^5$ ways
to choose the suits.  Therefore, there are $9 \cdot 4^5$ such hands.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} An adequately-prepared 6.042 student has
the following texts:

\begin{itemize}
\item 5 copies of Cupillari
\item 2 copies of Rosen, 3rd edition
\item 6 copies of Rosen, 4th edition
\item 4 copies of the Fall 97 lecture notes
\end{itemize}

Copies of the same text are indistinguishable.  The student also has
a bookshelf with four distinguishable shelves.  In how many different
ways can the student arrange his texts on his bookshelf?  Assume that
each shelf has enough space to hold all of the texts and that two
arrangements are different if the texts appear in a different order on
a shelf.

\solution{Each arrangement of the texts on the bookshelf corresponds
to a sequence of the texts together with three ``dividers''.  The
texts on the first shelf appear in the sequence before the first
divider, the texts on the second shelf appear between the first and
second dividers, etc.  Thus, the number of different arrangements is

\[
\frac{20!}{5! \ 2! \ 6! \ 4! \ 3!}.
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Before he formed the legendary Knights of
the Round Table, King Arthur experimented with some other
organizations.

\begin{problemparts}

\problempart After Arthur first selected his knights, he lined them up
for review.  Four of the knights were armored from head to toe and
were consequently indistinguishable from one another.  The other eight
knights were unarmored and could be distinguished.  In how many
different ways could Arthur line up the knights for review?

\solution{If all of the knights were distinguishable, then there would
be $12!$ ways to line them up.  However, since the order of the four
armored knights is irrelevant, there are $12! / 4!$ ways to line all
the knights up for review.}

\problempart In the early days, Arthur's 12 knights simply traveled
about on horseback in single file.  By now, Arthur could distinguish
all his knights, armored or not.  However, Sir Lancelot insisted that
he ride somewhere ahead of Sir Gawain and somewhere behind Sir
Percival.  In how many different ways could Arthur arrange his mounted
knights in single file?

\solution{There are $12!$ arrangements, neglecting the special rule
involving Lancelot, Gawain, and Percival.  Among these $12!$
arrangements, these three knights appear in each of the $3!$ possible
orders an equal number of times.  In particular, there are $12! / 3!$
arrangements with Percival ahead of Lancelot ahead of Gawain.}

\problempart While Camelot was under construction, Arthur seated his
band of 12 knights around a hexagonal table, with two knights on each
side.  Two seatings were considered equivalent if one could be
obtained from the other by rotating the table.  In how many different
ways could Arthur seat the Knights of the Hexagonal Table?

\solution{Ignoring rotations, there are $12!$ possible seatings.
Since there are 6 possible ways to rotate the table, the number of
seatings is $12! / 6$.
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} Solve the following counting problems, and
explain your answers.

\begin{problemparts}

\problempart Determine the number of solutions to the equation $x_1 +
x_2 + \ldots + x_n = r$, where all variables are non-negative
integers.

\solution{Each solution to the equation corresponds to a string of $r$
stars and $n-1$ bars.  The correspondence is illustrated by the
example below, where $n = 4$ and $r = 6$.

\[
\begin{array}{ccccccccc}
\star \star \star & \mid & \star & \mid & & \mid & \star \star \\
3 & + & 1 & + & 0 & + & 2 & = & 6
\end{array}
\]

Therefore, the number of solutions is
\[
\binom{n + r - 1}{r}.
\]
}

\problempart Determine the number of sequences of $k$ integers in the
range $0$ to $n$ that are {\em increasing}; that is, each integer in
the sequence is greater than or equal to the one before.

\solution{Each sequence corresponds to a string of $n$ stars and $k$
bars.  The correspondence is illustrated below, where $k = 4$ and $n =
7$.

\[
\begin{array}{ccccccccc}
\star \star \star & \mid & \star & \mid & & \mid & \star \star & \mid & \star\\
3 &,& 4 &,& 4 &,& 6
\end{array}
\]

As the example illustrates, the $k$-th number in the sequence is equal
to the total number of stars preceding the $k$-th bar.  Therefore, the
number of sequences is
\[
\binom{n + k}{k}.
\]
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} Consider the following procedure for
generating a small, positive integer.  I flip a coin.  If the outcome
is heads, then I roll one die and take the result.  If the outcome is
tails, then I roll two dice and take the sum.  Assume that the coin is
fair and the dice are fair and 6-sided.

\begin{problemparts}
\problempart Define a probability space that describes this experiment.

\solution{The sample space consists of 42 outcomes.  Six of these are
pairs:

\[
(H, 1), (H, 2), \ldots, (H, 6)
\]

Each of these outcomes occurs with probability $\frac{1}{2} \cdot
\frac{1}{6} = \frac{1}{12}$.  The remaining thirty-six outcomes are
triples:

\[
(T, 1, 1), (T, 1, 2), \ldots, (T, 6, 6)
\]

Each of these outcomes occurs with probabiliy $\frac{1}{2} \cdot
\frac{1}{6} \cdot \frac{1}{6} = \frac{1}{72}$.}

\problempart What is the probability that the procedure generates a 5?

\solution{
\begin{eqnarray*}
\Pr(\text{generates 5})
	& = &	\Pr((H, 5)) + \Pr((T, 1, 4)) + \Pr((T, 2, 3)) \\
	&   &	\mbox{}	+ \Pr((T, 3, 2)) + \Pr((T, 4, 1)) \\
	& = &	\frac{1}{12} + \frac{1}{72} + \frac{1}{72}
		+ \frac{1}{72} + \frac{1}{72} \\
	& = &	\frac{5}{36}
\end{eqnarray*}
}

\problempart What is the probability that the coin was heads given
that the procedure generated a 5?

\solution{
\begin{eqnarray*}
\Pr(\text{coin was heads} \mid \text{generated 5})
	& = &	\frac{\Pr(\text{coin was heads} \cap \text{generated 5})}
			{\Pr(\text{generated 5})} \\
	& = &	\frac{\Pr((H, 5))}{\frac{5}{36}} \\
	& = &	\frac{\frac{1}{12}}{\frac{5}{36}} \\
	& = &	\frac{3}{5}
\end{eqnarray*}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} Each person carries a certain, rare disease
with probability 1 in 1000.  Two doctors claim to be able to test for
the disease before symptoms appear.

\begin{problemparts}

\problempart Doctor $A$ was educated at Harvard Medical School and
employs the latest high-tech test.  If a patient has the disease, then
the test comes back positive 99\% of the time.  If the patient does
not have the disease, then the test comes back negative 97\% of the
time.  What is the probability that Doctor $A$ correctly diagnoses a
patient?

\solution{
\begin{eqnarray*}
\Pr(\text{$A$ is correct})
	& = &	\Pr(\text{is diseased} \cap \text{test positive}) \\
	&   &	\mbox{} +
		\Pr(\text{not diseased} \cap \text{test negative}) \\
	& = &	\Pr(\text{is diseased}) \cdot
		\Pr(\text{test positive} \mid \text{is diseased}) \\
	&   &	\mbox{} +
		\Pr(\text{not diseased}) \cdot
		\Pr(\text{test negative} \mid \text{not diseased}) \\
	& = &	0.001 \cdot 0.99 + 0.999 \cdot 0.97 \\
	& \approx &	0.970
\end{eqnarray*}
}

\problempart Doctor $B$ murmurs strange chants and burns incense.
With probability 1 in 1000, Doctor $B$ says that a patient has the
disease, regardless of whether or not the patient actually does.  What
is the probability that Doctor $B$ correctly disgnoses a patient?

\solution{
\begin{eqnarray*}
\Pr(\text{$B$ is correct})
	& = &	\Pr(\text{is diseased} \cap \text{test positive}) \\
	&   &	\mbox{} +
		\Pr(\text{not diseased} \cap \text{test negative}) \\
	& = &	\Pr(\text{is diseased}) \cdot
		\Pr(\text{test positive} \mid \text{is diseased}) \\
	&   &	\mbox{} +
		\Pr(\text{not diseased}) \cdot
		\Pr(\text{test negative} \mid \text{not diseased}) \\
	& = &	0.001 \cdot 0.001 + 0.999 \cdot 0.999 \\
	& \approx &	0.998
\end{eqnarray*}
}

\problempart Which doctor makes more errors?

\solution{Doctor $A$ makes about 15 times more errors than Doctor
$B$.}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (15 points)} There are three prisoners, $A$, $B$, and
$C$.  The parole board will to release two of the prisoners, but has
not yet announced which two.  The pair to be released is selected by
the board uniformly at random; that is, each of the three pairs of
prisoners has a $\frac{1}{3}$ probability of being chosen.

Prisoner $A$ figures that he will be released with probability
$\frac{2}{3}$.  A guard offers to tell prisoner $A$ the name of one of
the other prisoners who will be released (either $B$ or $C$).
However, prisoner $A$ declines the offer.  He reasons that if the
guard says, for example, ``$B$ will be released'', then his own
probability of release will drop to $\frac{1}{2}$.  This is because he
will then know that either he or $C$ will be released, and these two
events are equally likely.

Either prove that prisoner $A$ has reasoned correctly or prove that he
is wrong.  Assume that if the guard has a choice of saying either $B$
or $C$, because both are to be released, then he picks one at random
with equal probability for each.

\solution{Prisoner $A$ is wrong.  He is conditioning on the event that
prisoner $B$ is to be released and not on the event that the guard
says prisoner $B$ is to be released.  A correct calculation is given
below.

\begin{eqnarray*}
\Pr(\text{$A$ is released} \mid \text{guard says $B$})
	& = &	\frac{\Pr(\text{$A$ is released} \cap \text{guard says $B$})}
			{\Pr(\text{guard says $B$})} \\
	& = &	\frac{\Pr(\text{$A$ and $B$ are released})}
			{\Pr(\text{guard says $B$})} \\
	& = &	\frac{\frac{1}{3}}{\frac{1}{2}} \\
	& = &	\frac{2}{3}
\end{eqnarray*}

Thus, the probability that prisoner $A$ will be released is not
changed by what the guard tells him.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} What is the probability that a random poker
hand contains cards from at most two suits?

\solution{The sample space consists of the $\binom{52}{5}$ possible
hands.  Each hand is equally likely and comes up with probability $1 /
\binom{52}{5}$.  Therefore, the probability that a hand contains at
most two suits is equal to the number of different hands of this type
multiplied by $1 / \binom{52}{5}$.  All that remains is to count the
number of poker hands with at most two suits.

There are $\binom{4}{2}$ ways to choose two suits and $\binom{26}{5}$
ways to choose five cards from these two suits.  However, this
triple-counts hands containing cards from a single suit.  (For
example, a hand with all spades is counted once as a spades-hearts
hand, a second time as a spades-clubs hand, and a third time as a
spades-diamonds hand.)  The number of hands with a single suit is $4
\cdot \binom{13}{5}$.  Therefore, the number of hands with at most two
suits is

\[
\binom{4}{2} \cdot \binom{26}{5} - 2 \cdot 4 \cdot \binom{13}{5}.
\]

The probability that a random poker hand contains cards from at most
two suits is:

\begin{eqnarray*}
\Pr(\text{hand has at most two suits})
	& = & \frac{\binom{4}{2} \cdot \binom{26}{5} -
			2 \cdot 4 \cdot \binom{13}{5}}
		{\binom{52}{5}} \\
	& \approx & 0.15
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems} \end{document}
