\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\askaboutsolutions
\begin{document}
\pset{8}{April 17, 2001}{2:35pm in lecture, April 24, 2001}
\renewcommand{\labelenumi}{\bf (\alph{enumi})}
\renewcommand{\labelenumii}{\bf (\roman{enumi})}
\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

\paragraph{Reading}
Rosen, \textit{Discrete Mathematics and Its Applications},
Sections 4.4 and 4.5


\vspace{-.25in}

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
mention their names on top of the problem set. If you did not
collaborate with anyone, you should explicitly say so. As a reminder,
the write-up of your solutions should be entirely your own.

\paragraph{Self-study}

The following exercises are \emph{optional;} do them if you think you
need the practice. The mini-quiz in tutorial on Friday will draw
(only) from these problems.

Exercises from Rosen (answers in the back of the book): 
Section 4.4: 9, 11, 13, 15, 17, 19, 21, 28, 31, 33.


\medskip
\begin{problems} 
                     
% Fall 98 Pset 8
\problem \goals{closed-forms} {\bf (10 points)} Find generating functions for the following
sequences.

\begin{problemparts}

\problempart $< 0, 0, 1, 1, 1, 1, 1, \ldots >$

\solution{
\begin{eqnarray*}
x^2 + x^3 + x^4 + x^5 + x^6 + \ldots
        & = &   x^2 \cdot (1 + x + x^2 + x^3 + x^4 + \ldots) \\
        & = &   \frac{x^2}{1-x}
\end{eqnarray*}
}

\problempart $< 0, 2, 4, 6, 8, 10, \ldots >$

\solution{
\begin{eqnarray*}
0 + 2 x +  4 x^2 + 6 x^3 + 8 x^4 + \ldots
        & = &   2x \cdot (0 + 1 + 2 x + 3 x^2 + 4 x^3 \ldots) \\
        & = &   2x \cdot \frac{d}{dx} \ (1 + x + x^2 + x^3 + x^4 + \ldots) \\
        & = &   2x \cdot \frac{d}{dx} \ \left(\frac{1}{1-x} \right)\\
        & = &   \frac{2x}{(1-x)^2}
\end{eqnarray*}
}

\problempart $< 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
1 + x^3 + x^6 + x^{9} + x^{12} + \dots  & = &   \frac{1}{1 - x^3}
\end{eqnarray*}
}

\problempart $< 2^0, 2^1, 2^2, 2^3, 2^4, 2^5, \ldots  >$

\solution{
\begin{eqnarray*}
\lefteqn{2^0 + 2^1 x + 2^2 x^2 + 2^3 x^3 + 2^4 x^4 + \ldots}
\hspace{1in} \\
        & = &   (2x)^0 + (2x)^1 + (2x)^2 + (2x)^3 + (2x)^4 + \ldots \\
        & = &   \frac{1}{1 - 2x}
\end{eqnarray*}
}

\problempart $< -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{-1 + x^2 - x^3 + x^5 - x^6 + x^8 - \ldots}
\hspace{1in} \\
        & = & (x^2 + x^5 + x^8 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
        & = & x^2 (1 + x^3 + x^6 + \ldots) - (1 + x^3 + x^6 + \ldots) \\
        & = & (x^2 - 1) \cdot (1 + x^3 + x^6 + \ldots) \\
        & = & \frac{x^2 - 1}{1 - x^3}
\end{eqnarray*}
}

\end{problemparts}

%Fall 98 Pset 8

\problem \goals{closed-forms} {\bf (10 points)} 
Suppose that $f(x)$ is the generating function for the sequence $a_0,
a_1, a_2, \ldots$.  Find generating functions for the following
sequences.

\begin{problemparts}
\problempart $< 0, 0, 0, a_0, a_1, a_2, \ldots >$

\solution{
\begin{eqnarray*}
a_0 x^3 + a_1 x^4 + a_2 x^5 + \ldots
        & = &   x^3 \cdot (a_0 + a_1 x + a_2 x^2 + \ldots) \\
        & = &   x^3 f(x)
\end{eqnarray*}
}

\problempart $< a_0, a_1 + 1, a_2 + 2, a_3 + 3, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + (a_1 + 1) x + (a_2 + 2) x^2 + (a_3 + 3) x^3 + \ldots}
\hspace{1in} \\
        & = &   (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)
                + (0 + 1 x + 2 x^2 + 3 x^3 + \ldots) \\
        & = &   f(x) + \frac{x}{(1 - x)^2}
\end{eqnarray*}
}

\problempart $< a_0, 0, a_1, 0, a_2, 0, a_3, 0, \ldots >$

\solution{
\begin{eqnarray*}
a_0 + a_1 x^2 + a_2 x^4 + a_3 x^6 + \ldots
        & = &   f(x^2)
\end{eqnarray*}
}

\problempart $< a_0, -a_1, a_2, -a_3, a_4, \ldots >$

\solution{
\begin{eqnarray*}
a_0 - a_1 x + a_2 x^2 - a_3 x^3 + a_4 x^4 - \ldots
        & = &   f(-x)
\end{eqnarray*}
}

\problempart $< a_0, 0, a_2, 0, a_4, 0, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + a_2 x^2 + a_4 x^4 + a^6 x^6 + \ldots}
\hspace{1in} \\
        & = &   \frac{1}{2} (
                (a_0 - a_1 x + a_2 x^2 - a_3 x^3 + \ldots) \\
        &   & \mbox{} + (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)) \\
        & = &   \frac{1}{2}(f(-x) + f(x))
\end{eqnarray*}
}

\end{problemparts}

% Fall 98 Pset 9
\problem \problem \goals{Discrete Probability, probabilities} {\bf (10 points)} Three gunfighters, $A$, $B$, and~$C$, plan
to fight a three-cornered pistol duel. They all know that $A$'s chance
of hitting his target is $0.3$, $B$~never misses, and $C$'s chance of
hitting is~$0.5$. They will shoot one at a time in the sequence
$ABCABC\ldots$. On his turn, a gunfighter may target either of the
other two, or may fire harmlessly into the air. Assume that each
gunfighter uses the shooting strategy that maximizes his probability
of being the only one left standing. What should gunfighter $A$~do on
his first shot and what probability of survival does this give him?

\solution{\textbf{Solution:}
  
  First note that the optimal strategy for~$B$ is to shoot the most
  accurate gunfighter. So, if $B$~gets to shoot and both $A$ and~$C$
  are still alive, $B$~will shoot~$C$---this gives him a $1-0.3 = 0.7$
  chance of survival---and not~$A$---that would only give him a $1-0.5
  = 0.5$ chance of survival.
  
  Suppose that $A$ shoots into the air. Then $B$ shoots~$C$, and
  $A$~gets one shot to kill~$B$ before he himself is killed. Therefore
  $A$~has a $0.3$~chance of survival.
  
  Suppose that $A$ shoots at~$B$. If he hits, then he enters a duel
  with~$C$, where $C$ gets the first shot. In this case, let $p$~be
  the probability that $A$~wins the duel. For this to happen, either
  $C$~must miss and $A$~must hit (probability $0.5 \cdot 0.3$) or else
  $C$~must miss, $A$~must miss, and then $A$ must win a duel of the
  same type as before (probability $0.5 \cdot 0.7 \cdot p$).  As an
  equation:
  \begin{displaymath}
    p = \frac{1}{2} \cdot \frac{3}{10} + \frac{1}{2} \cdot \frac{7}{10} p,
  \end{displaymath}
  which has the solution $p = 3 /13$.
  
  Thus, If $A$ hits~$B$, his odds of survival are lower than if he
  fires into the air! If he does not hit, his probability of survival
  is the same as if he had started by firing in the air. Since
  $A$~hits with probability~$0.3$, the probability that $A$~survives
  when he begins with shooting at~$B$ is $0.3 \cdot 3 / 13 + 0.7 \cdot
  0.3 = 363 / 1300 < 0.28$.
  
  On the other hand, suppose that $A$ shoots at~$C$. If he hits, then
  $B$~immediately kills him. If he does not hit, his probability of
  survival is, again, the same as if he had started by firing in the
  air. Thus, his probability of survival in this case is $0.3 \cdot 0
  + 0.7 \cdot 0.3 = 0.21$.
  
  To conclude, $A$'s best strategy is to fire into the air; this gives
  him a $0.3$ chance of survival.}


%Spring 99 Pset 9

\problem \goals{Discrete Probability, probabilities} {\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 probability $\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*}
}

\end{problemparts}

% Spring 99 Pset 10
\problem \goals{Discrete Probability, probabilities, counting} {\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}} \\
        & = & \frac{88}{595} \approx 0.15
\end{eqnarray*}
}

%pset9 problem1 spring98
\problem \goals{Discrete Probability, probabilities} [10 pts]

Suppose the game \emph{Let's Make A Deal} is changed slightly. Instead
of having 3 doors with 1 grand prize, in the new game there are 4
doors with 2 grand prizes. The rule of the game remains the
same. Therefore the game now becomes:
\begin{quote}
  At one stage of the game, a contestant is shown 4 doors. The
  contestant knows that there are 2 grand prizes behind 2 of the
  doors and that there are goats behind the 2 other doors. At the
  beginning, the contestant picks a door. To build suspense, the
  assistant of the game then opens a \emph{different} door, revealing
  a goat. The contestant can then stick with his original door or
  switch to another unopened door. He wins a prize only if he now
  picks the door with the prize.
\end{quote}
In the new game, what is the probability of winning with the ``stick''
strategy?  How about the ``switch'' strategy? Can you explain why the
two probabilities do not sum up to 1?

\solution{
{\bf Solution}

The player wins with a ``stick'' strategy iff he chooses the ``correct
door'' in the first place. Therefore the probability of winning with
the ``stick'' strategy is $\frac{1}{2}$.

To calculate the probability of winning with a ``switch'' strategy,
we use a tree diagram.  The prize location can initially be any one of the pairs ${(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}$ each with probability $\frac{1}{6}$.  Because of the symmetry in the tree, we consider the following sub-tree for the pair $(1,4)$.

\bigskip
\centerline{\resizebox{!}{7.0in}{\includegraphics{figures/ps8-monty}}}
\bigskip

Therefore we get that:

\begin{eqnarray*}
  P(\mbox{winning with ``switch'' strategy})
  &=& \mbox{\# of prize combinations} \cdot P(\mbox{winning with ``switch'' strategy for (1,4)})\\
  &=& 6 \cdot (4 \cdot \frac{1}{48} + 4 \cdot \frac{1}{96})\\
  &=&\frac{3}{4}
\end{eqnarray*}

The two probabilities do not need to sum up to 1. This is because the
two strategies are not mutually exclusive, that is there are some
strategies for which the player would win whether or not he ``sticks''
or ``switches''.  For example, if the prizes are behind doors 1 and 4, and the player chooses 1 first then switches to 4, then he would have won
by either strategy.  Therefore, the same winning event can be counted
in both cases at the same time.  }

\end{problems}

\end{document}                            

