\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal and Prof.~Charles E. Leiserson}

\begin{document}
\inclassproblems{9, Mon}

\begin{problem}
Theory Hippo recently lost a lot of money playing poker with the 6.042
staff.  So, Theory Hippo has decided to spend a week in Las Vegas
studying gambling.  The hotel manager told Theory Hippo that a full
house (three-of-a-kind and one pair) is much more valuable than two
pairs.  Since Theory Hippo is not so sure, he decides to count the
number of hands with two pairs, but no three- or four-of-a-kind.  In
other words, the hand $\ang{9\clubsuit, 9\diamondsuit, 8\clubsuit,
8\heartsuit, 7\spadesuit}$ is considered two pairs, but
$\ang{9\clubsuit, 9\diamondsuit, 8\clubsuit, 8\heartsuit,
9\heartsuit}$ and $\ang{9\clubsuit, 9\diamondsuit, 9\heartsuit,
9\spadesuit, 7\clubsuit}$ are not.

Theory Hippo reasons that there are 13 choices for the value of the
cards in the first pair.  Then, there are $\binom{4}{2} = 6$ ways to
choose $2$ of the $4$ cards in the deck that have this value.  That
leaves $12$ choices for the value of the cards in the second pair, and
$\binom{4}{2} = 6$ ways to choose $2$ of the $4$ cards with this
value.  Finally, the fifth card can be any one of the $44$ cards
remaining in the deck, because the fifth card can not have the same
value as the first two pairs leaving $48-4$ possibilities.  Altogether
there are $13 \cdot 6 \cdot 12 \cdot 6 \cdot 44 = 247,104$ hands with
just two pairs.

Is Theory Hippo's argument correct?  If so, prove it by arguing that
everything has been counted exactly once.  If not, explain why and how
to fix it.

\solution{(Also in the Course Notes.)  The argument is incorrect.  The
bug is that every hand has been counted twice!  For example, a pair of
kings and a pair of queens is counted once with the kings as the first
pair and a second time with the queens as the first pair.  The
references in the argument to a ``first pair'' and a ``second pair''
signal danger; these terms imply an ordering that is not part of the
problem. There is a 2-to-1 mapping from the set of hands we counted to
the set of hands with two pairs.  Therefore, the set of hands with two
pairs is half as large as our initial count:
\begin{eqnarray*}
\mbox{hands with two pairs}
        & = & \frac{13 \cdot 6 \cdot 12 \cdot 6 \cdot 44}{2} \\
        & = & 123,552.
\end{eqnarray*}
The course notes show an alternate way of counting the hands with
two-pairs, and one can verify by comparing the two answers.  But, in
any counting argument, one must keep track of whether order is
important and make sure that things are counted only once.

A two-pairs hand turns out to be $33$ times more likely than a full
house.  }
\end{problem}




% % source: spring00 ps7
% % topic: combinations
% \begin{problem}
% On the faculty of a school's EECS department (down the river
% somewhere\ldots) there are 14~hackers and 8~theoreticians. 
% \begin{problemparts}
% 
% \problempart How many ways are there to select a committee of
% 6~members if \emph{exactly}~1 hacker must be on the committee?
% Express your answer in terms of binomial coefficients.
% 
% \solution{
% There are $\binom{14}{1}$ ways to choose the hacker and
% $\binom{8}{5}$ ways to choose the 5~theoreticians. So, in total, we
% have $\binom{14}{1}\binom{8}{5}$ ways to form the committee.
% }
% 
% \problempart 
% How many ways are there to select a committee of 6~members if \emph{at
% least}~1 hacker must be on the committee? 
%   
% \solution{
% The easiest way to solve this problem is to count the
% complement. There are $\binom{22}{6}$ different committees, and
% $\binom{8}{6}$ committees of just theoreticians. So there are
% $\binom{22}{6} - \binom{8}{6}$ different possibilities.
% 
% Alternatively, we can count all possible combinations of people such
% that there is at least one hacker in every combination, but we must
% remember not to count any combination multiple times. We can have
% committees with:
% \begin{itemize}
% \item 1 hacker, 5 theoreticians: $\binom{14}{1}\binom{8}{5}$,
% \item 2 hackers, 4 theoreticians: $\binom{14}{2}\binom{8}{4}$,
% \item 3 hackers, 3 theoreticians: $\binom{14}{3}\binom{8}{3}$,
% \item 4 hackers, 2 theoreticians: $\binom{14}{4}\binom{8}{2}$,
% \item 5 hackers, 1 theoretician: $\binom{14}{5}\binom{8}{1}$,
% \item 6 hackers, 0 theoreticians: $\binom{14}{6}\binom{8}{0}$.
% \end{itemize}
% So there are 
% $$
% \binom{14}{1}\binom{8}{5} + 
% \binom{14}{2}\binom{8}{4} + 
% \binom{14}{3}\binom{8}{3} + 
% \binom{14}{4}\binom{8}{2} + 
% \binom{14}{5}\binom{8}{1} + 
% \binom{14}{6}\binom{8}{0}
% $$ 
% different possibilities.
% }
% 
% \problempart 
% How many ways are there to select a committee of 6~members if \emph{no
% more than}~2 hackers can be on the committee?  
% 
% \solution{
% There are again many ways to count this, but the key is to make sure 
% that nothing is counted twice. Here is one way:
% \begin{itemize}
% \item no hacker, 6 theoreticians: $\binom{8}{6}$,
% \item 1 hacker, 5 theoreticians: $\binom{14}{1}\binom{8}{5}$,
% \item 2 hackers, 4 theoreticians: $\binom{14}{2}\binom{8}{4}$,
% \end{itemize}
% for a total of 
% \begin{equation} \label{eq:sum}
% \binom{8}{6}+\binom{14}{1}\binom{8}{5}+\binom{14}{2}\binom{8}{4}
% \end{equation}
% ways.
% }
% 
% \problempart
% Check that your answers to parts~(b) and~(c) are correct by arguing
% that (i)~everything has been counted at least once and that
% (ii)~nothing has been counted multiple times. 
% 
% \solution{
% The idea of this part of the problem is not to give a rigorous proof 
% but to be able to argue why someone should believe your answer (why
% you should believe your own answer!). We give an argument for
% part~(c).
% 
% To see why every committee is counted, it suffices to observe that
% every committee of no more than 2 hackers must  contain 
% \begin{itemize}
% \item no hackers at all, or
% \item 1 hacker, or
% \item 2 hackers.
% \end{itemize}
% In any one of these three cases, the committee \emph{is} going to be
% counted, by the corresponding term in the sum~\eqref{eq:sum}.
% 
% To see why no committee is counted more than once, first observe that
% no committee can fall into more than one of the three cases above. So,
% every committee is counted by exactly one of the terms
% in~\eqref{eq:sum}. Moreover:
% \begin{itemize}
% \item 
% If the committee is counted in by the first term, then it is counted
% exactly once, by the definition and relevant theorems concerning
% combinations.
% 
% \item
% If the committee is counted in by the second term, then it is counted
% exactly once, because \emph{the choices that correspond to the two
% terms of the product} (choice of the hacker, choice of the
% theoreticians) \emph{are not interchangeable} (in the sense explained
% in class).
% 
% \item 
% If the committee is counted in by the third term, the committee is
% counted exactly once, again, for reasons similar to the previous case.
% 
% \end{itemize}
% A similar argument can be given for our counting in part~(b).
% }
% 
% \end{problemparts}
% \end{problem}

% new: RAD
\begin{problem}
One algorithm for checking whether an arbitrary labeled graph is
$3$-colorable is to enumerate all possible $3$-color assignments for
the vertices of the graph and then test each color assignment to see
if it is a valid coloring.  We are going to count the maximum number
of color assignments that this algorithm may have to test.  (In other
words, what is the worst-case behavior of this approach?)

Let $G=(V,E)$ be an $n$-vertex graph with vertex set $V = \set{v_1,
v_2,\ldots, v_n}$, and let $C=\set{R,G,B}$ be the set of colors.  A
\emph{color assignment} is a function $f:V\to C$.  (\emph{Note:} a
\emph{valid} coloring is one where $f(u)\neq f(v)$ for all $(u,v)\in
E$, that is, no two adjacent vertices in the graph have the same
color.  We will not be concerned much with validity in this problem.)
\begin{problemparts}

\problempart How many different color assignments are there?  (Colors
are not interchangable.)

\solution{
This is exactly the number of functions from an $n$-element set (the
vertices of $G$) to a $3$-element set (the colors). We know there
are~$3^n$ such functions.
}

\problempart There are much easier ways to check if a graph can be
colored with $1$ color or $2$ colors.  Therefore, we are really only
interested in color assignments that use \emph{exactly}~3 colors.  How
many ways can we color the vertices of $G$, so that all three colors
in $C$ are used?

\solution{
Let $A_i$ be the set of all colorings that use \emph{exactly}~$i$
colors, for $i=1,2,3$, so that we are after $|A_3|$. Clearly, $A_1$,
$A_2$, $A_3$ are disjoint, so  
$$
|A_1 \cup A_2\cup A_3| = |A_1| + |A_2| + |A_3|\ ,
$$
and they cover the entire set of 3-colorings of $G$, so 
$$
|A_1 \cup A_2\cup A_3| = 3^n\ ,
$$
by the previous part. Hence, to calculate $|A_3|$, we combine these
two equations to get 
\begin{equation}\label{eq:a}
|A_3| = 3^n - |A_2| - |A_1|\ ,
\end{equation}
so that it suffices to calculate $|A_2|$ and $|A_1|$. 

The number $|A_1|$ of colorings that use exactly one color is easily
seen to be
\begin{equation}
|A_1| = 3\ ,
\end{equation}
because, once we pick one of the $3$ colors, the numbering is fully
specified. 

To find the number $|A_2|$ of colorings that use exactly $2$ colors,
we first observe that 
$$
A_2 = A_{RG} \cup A_{GB} \cup A_{BR},
$$
where $A_{RG}$ is the set of colorings that use \emph{both} red
\emph{and} green; and similarly for $A_{GB}$ and $A_{BR}$.  Since these
three sets are disjoint and all have the same size, we have 
\begin{equation}
|A_2| = |A_{RG}| + |A_{GB}| + |A_{BR}| = 3|A_{RG}|\ ,
\end{equation}
and we need to find $|A_{RG}|$ only. 

Now, we know that the total number of colorings that use red and green
(but maybe not both of them) is $2^n$. Among these colorings only two
fail to use both colors: the ``all-red'' coloring and the
``all-green'' one. Thus, we have 
\begin{equation}\label{eq:d}
|A_{RG}| = 2^n - 2.
\end{equation}

Combining Equations~\eqref{eq:a}--\eqref{eq:d} yields
$$
|A_3| = 3^n - 3(2^n-2) - 3 = 3^n - 3\cdot 2^n + 3\ .
$$
}

\problempart For a graph with $3$ vertices we can see that the number
of color assignments with exactly $3$ colors are just the number of
possible permutations of $R$, $G$, $B$, which is $3!$.  Verify that
your formula in part~(b) gives the right answer for a $3$-vertex
graph.

\solution{
$3^3 - 3\cdot 2^3 + 3 = 27 -24 +3 = 6 = 3!$.

The formula $3! \binom{n}{3} 3^{n-3}$, which is likely to be
suggested by several tables as the correct solution to part~(b),
returns the correct value for $n=3$:
$$
3! \binom{3}{3} 3^{3-3} = 6\cdot 1\cdot 1 = 6\ ,
$$
but it tragically fails for other values, e.g., $n=4$:
$$
3! \binom{4}{3} 3^{4-3} = 6\cdot 4\cdot 3 = 72 \neq 
36 = 3^4 - 3\cdot 2^4 + 3\ .
$$
\emph{Always sanity-check your formulas on special cases, but don't
trust ``proof by example.''}}

\problempart Even so, many of the assignments are redundant. For
example,in a $4$-vertex graph, the color assignment $RGBB$ is
essentially the same as $RBGG$, because if one fails, the other does
also.  In general, any two colorings are equivalent if one assignment
can be achieved from the other by just swapping color names.  If we
remove these redundant color assignments, how much can we improve our
number from part~(b)?

\solution{ Consider the binary relation on $A_3$ that relates a
coloring $c$ to another coloring $c'$ iff $c'$ can be obtained from
$c$ via a permutation of the colors. One can easily check this is an
equivalence relation, that breaks $A_3$ into equivalence classes of
$3!=6$ members each. (To see why $6$ is the size of an equivalence
class: if you pick any coloring $c$ from the class and apply to it all
$3!=6$ possible permutations of the $3$~colors, you are certain to
derive all members of the class exactly once.)

We want to count the number of these equivalence classes.  But, since
the classes are disjoint, cover the entire $A_3$, and all have
size~$6$, their number must be
$$
\frac{|A_3|}{6} = \frac{3^n - 3\cdot 2^n + 3}{6}\ .
$$
}
\end{problemparts}
\end{problem}


\end{document}
