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

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{8M}





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

He 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 two of the four 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 two of the four
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$ hand with just two pairs.

Is this argument correct? If it is not, explain why and how to fix
it. If it is correct, prove it by arguing that everything has been
counted exactly once.

\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 two pair hands, and
one can verify by comparing the two answers. But it is important in
any counting argument to keep track of whether order is important or
not and make sure that things are counted only once.

Two pairs turn 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~theoriticians. 
\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? (You may express 
this 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~theoriticians. 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 committe \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
theoriticians) \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}
A possible algorithm for checking if an arbitrary labelled graph is
3-colorable is to enumerate all possible 3 color assignments for the
nodes 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$ be a $n$ node graph with vertices labelled $v_1$ through
$v_n$. Let the set of colors $C=\{R,G,B\}$. A \emph{color assignment} 
is a function from the set of labelled nodes $G$ to the set of colors
$C$; a \emph{valid} coloring is one where no two adjacent nodes in $G$ 
have the same color, however we will not be concerned much with
validity in this problem.
\begin{problemparts}

\problempart 
How many different ways can you assign colors from $C$ to
the nodes of $G$? (Note that colors are not interchangable.)

\solution{
This is exactly the number of functions from an $n$-element set (the
nodes 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 one
color or two colors. Therefore we are really only interested in color
assignments that use \emph{exactly}~3 colors. How many ways can we
color the nodes 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|$, $|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 two 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}$, $A_{BR}$. Easily, these
three sets are disjoint and all have the same size. So  
\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. So, 
\begin{equation}\label{eq:d}
|A_{RG}| = 2^n - 2.
\end{equation}

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

\problempart 
For a graph with three nodes 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-node graph. 

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

Note that the formula $3! \binom{n}{3} 3^{n-3}$ (suggested by several
tables this morning 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 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.
$$
So, \emph{always test your formula on special cases, but never trust
your special tests}.
}

\problempart 
Even so, many of the assignments are redundant. For
example for a four node graph the color assignment $RGBB$ is
essentially the same as $RBGG$, because if one fails the other will 
also. In general, any two colorings are equivalent if one assignment
can be achieved from the other just by 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.) 

Clearly, 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}



% source: old
% last used: fall 01 pset (similar version, but not same)
% topics: division rule, bijections
\begin{problem}
\begin{problemparts}
\problempart 
Suppose that Theory Pig wants to take a walk on his neighborhood grid
to location $(n,n)$. He starts at position $(0, 0)$.  At any time, he
can step north (incrementing the first coordinate) or step east
(incrementing the second coordinate).  

\problempart 
In how many different ways can he reach position $(n,n)$, where $n$ is
a non-negative integer? 

\solution{
Theory Pig must take $2n$ steps in total.  Of these, he must
choose a subset of $n$ to be north steps.  This gives $\binom{2n}{n}$  
different ways to reach $(n, n)$.
}

\problempart 
How many different ways are there to list the numbers $1,2,\ldots,2n$
such that the even numbers appear in increasing order and the odd
numbers appear in decreasing order? 

\solution{ 
There are $(2n)!$ ways to list the numbers $1,2,\ldots,n$.  We can
define a $n!$-to-1 mapping that takes an arbitrary listing to a
listing in which the even numbers are sorted in increasing order 
and the odd numbers remain as before.  Thus, by the Division Rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are
\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}
listings in which the even numbers are increasing and the odd numbers 
are decreasing.

Yet another argument: Of the total $2n$ positions in the sequence,
there are $\binom{2n}{n}$ ways to choose where the even numbers are
going to be. Once you make this choice, the positions of the odd
numbers are fully specified (just the unoccupied positions) and the
order of both the even and odd numbers is fully specified as
well. So, after this choice, there is exactly one way to determine the 
entire sequence. So there are as many sequences as many choices of
this kind, $\binom{2n}{n}$.
}

\problempart Describe a bijection that maps each one of Theory Pig's
paths to a listing of the numbers $1, 2, \ldots 2n$ with even numbers
increasing and odd numbers decreasing.

\solution{Each time Theory Pig take a step north, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step east, write an odd number, starting with $2n-1$ and working down.}
\end{problemparts}
\end{problem}

\end{document}
