\documentclass[12pt]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \prsol{9}{October 31, 2001}{\stamp}
\else
  \prprob{9}{October 29, 2001}{Wednesday, Oct. 31}{\stamp}
\fi

\reading \href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l9.pdf}
{Lecture Notes 9}. Rosen \S4.3 \S4.6 \S5.6

\ifshowsolutions{}\else
By 9am on the due date, send email to
\begin{center}
\href{mailto:6042-probs@theory.lcs.mit.edu?subject=Required\%20Reading\%20Comments\%20Week\%209}
{6042-probs@theory.lcs.mit.edu}
\end{center}
indicating in at most three sentences one or more of the following:
the passage in the reading---\emph{including its page number}---you
\begin{itemize}
\item found most difficult,
\item found most surprising,
\item would like to have discussed in the next Lecture.
\end{itemize}
\fi

\begin{problems}

\problem{Poker}

In the lecture notes, you have seen how to count all poker hands except
for \textbf{Straights}, \textbf{Flushes}, and \textbf{Straight Flushes}.
Remember you are dealing with a standard 52-card deck. \\
Indicate how many of five-card hands there are of each of the following
kinds:

\bparts

\ppart A \emph{Sequence} consists of consecutive cards of any suit,
such as 5H-6H-7S-8D-9C.
(An Ace may either be high (10-J-Q-K-A) or low (A-2-3-4-5), but can't go
around the corner: (Q-K-A-2-3) is \emph{not} a sequence.)

\solnospace{There are 10 possible choices for the lowest card which
determines uniquely the sequence of ranks, and 4 choices for the suit of
EACH card, so that we have $10*4^5 = 10240$ possible Sequence hands.}

\ppart A \emph{Matching Suit} is a hand of cards that are all of the same
suit.

\solnospace{There are 4 possible choices for the suit, and
$\dbinom{13}{5}$ for the set of 5 ranks within the 13 in the suit, so that
we have $4*\dbinom{13}{5} = 5148$ possible Matching Suits.}

\ppart A {\bf Straight Flush} is a hand that is \emph{both} a Sequence and
a Matching Suit.

\solnospace{There are 4 possible choices for the suit, and 10 for the
lowest card which determines uniquely the sequence of ranks, so that we
have $4*10 = 40$ possible Straight Flushes.}

\ppart A {\bf Straight} is a hand that is a Sequence but not a Matching
        Suit.

\solnospace{This is {\em exactly} the number of Sequence hands that are
not Straightes Flushes, so that we have $10240 - 40 = 10200$ possible
Straights.}

\ppart A {\bf Flush} is a hand that is a Matching Suit but not a Sequence.

\solnospace{This is {\em exactly} the number of Matching Suits that are
not Straight Flushes, so that we have $5148 - 40 = 5108$ possible
Flushes.}

\eparts

\problem{Magic !!!}

{\em Notations:}
\begin{itemize}
\item	{\em C} denotes {\em Clubs},
	{\em D} denotes {\em Diamonds},
	{\em H} denotes {\em Hearts},
	{\em S} denotes {\em Spades}. 
\item	{\em A} denotes {\em Ace},
	{\em K} denotes {\em King},
	{\em Q} denotes {\em Queen},
	{\em J} denotes {\em Jack},
	and the numbers denote their respective face values.
\item	A card is referred to by its kind followed by its suit.
	For example, {\em AS} is {\em Ace of Spades},
		{\em 10C} is {\em 10 of Clubs}, etc.
\end{itemize}

Remember the magical card trick from Lecture on 10/29 and this week's
Notes.  Using the following order of the 52 cards:
$AC < AD < AH < AS < 2C < 2D < 2H < 2S < 3C < ... < QS < KC < KD < KH < KS$,
see if you are capable of being:

\bparts

\ppart	The Assistant.

The public has drawn the following cards: {\em KH, 7C, 8H, JD, 7S}.  What
four-card sequence should you announce to the magician?
\solnospace{{\em 8H-JD-7C-7S}}

\ppart	The magician.

The assistant announced you the following cards: {\em QC, AD, 6S, 5D}.
What is the secret card?
\solnospace{{\em AC}}

\eparts

\problem{Binomial theorem}

Find the coefficient of $x^3$ in the following expressions:

\bparts

\ppart	$(x+1)^9$ ?

\solnospace{
$\dbinom{9}{3}*1^3*1^{9-3} = 84*1*1 = 84$
}

\ppart	$(2x+3)^5$ ?

\solnospace{
$\dbinom{5}{3}*2^3*3^{5-3} = 10*8*9 = 720$
}

\eparts

\problem{Mutinomials: ririririririririririvers !!!}

\bparts

\ppart	How many different permutations are there of the letters of MISSISSIPPI ?

\solnospace{
\[
\dbinom{11}{1,4,4,2} =\frac{11!}{1!4!4!2!} = 34650
\]
}

\ppart Suppose we have a generalized $n$-letter ``MISSISSIPPI'' word whose
letters break down as follows: $m$ occurrences of ``M'', $i$ occurrences
of ``I'', $s$ of ``S'', and $p$ of ``P''.  For example, for ``MISSISSIPI''
from the previous part, $(n,m,i,s,p) = (11,1,4,4,2)$.

Identify which formulas among the following describe the number of
different permutations of the generalized ``MISSISSIPI'' word:

\begin{enumerate}

\item	({\em True/False}): $\dbinom{n}{m,i,s,p}$

	\solnospace{True}

\item	({\em True/False}): $\dbinom{n}{p,i,m,s}$

	\solnospace{True}

\item	({\em True/False}): $\dbinom{n}{m,i,s,n-m-i-s}$

	\solnospace{True}

\item	({\em True/False}): $\dbinom{n}{m}\dbinom{n}{i}\dbinom{n}{s}\dbinom{n}{p}$

	\solnospace{False}

\item	({\em True/False}): $\dbinom{n}{m}\dbinom{m}{i}\dbinom{i}{s}\dbinom{s}{p}$

	\solnospace{False}

\item ({\em True/False}):
$\dbinom{n}{m}\dbinom{m-m}{i}\dbinom{n-m-i}{s}\dbinom{n-m-i-s}{p}$

	\solnospace{True}

\end{enumerate}

\eparts

\end{problems}

\end{document}

