\documentstyle[12pt]{cmu-art}
\def\la{\lambda}
\def\ni{\noindent}
%\def\tbt#1#2#3#4{\[\left( \begin{array}{cc}#1 & #2 \\ #3 & #4\end{array}
%\right)\]}
\def\tbt#1#2#3#4{\mbox{$\left( \begin{array}{cc}#1 & #2 \\ #3 & #4\end{array} \right)$}}
\newcounter{problem}

\newenvironment{problems}{\begin{enumerate}\setcounter{enumi}{\theproblem}}{\setcounter{problem}{\theenumi}\end{enumerate}}
%\newenvironment{problems}{\begin{enumerate}}{\end{enumerate}}

\pagestyle{empty}

\textheight 9.4in
\addtolength{\oddsidemargin}{-0.7in}
\addtolength{\textwidth}{1.2in}
\topmargin -0.3in
\headheight 0.1in
\headsep 0.1in

%\setlength{\textwidth}{6.50in}
%\addtolength{\oddsidemargin}{-0.75in}
%\addtolength{\evensidemargin}{-0.75in}
%\topmargin -1in

\begin{document}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ 10 Powerful Ideas\hfil 
Bruce Magss-neto}
\vskip 0.1in
\hbox to \hsize{\ \ \ QUIZ 3 REVIEW \hfil \today}
}}}

\noindent
\ \\

\noindent
\newcommand{\problem}[3]{\noindent {\bf #1}. [#2 points] \\ #3 \vspace{1ex}}

\newcommand{\wisdom}[2]{\begin{quotation}
 \begin{center} \bf #1 \end{center} #2 \end{quotation} }

\wisdom{The easy stuff.}{This part is to test your ability to study 
material that has been labeled as likely to appear 
on exams. If you do not do well on this section, your study habits could
use adjustment.}

\problem{1}{5}{
How many ways are there to seat $k$ children in $n>k$ chairs?
}
 
There are ${n}\choose{k}$ ways to choose which chairs will be filled,
and then $k!$ ways to choose the permutation of the children to fill
them, giving us a total of $k! {{n}\choose{k}} = \frac{n!}{(n-k)!}$ ways
to seat the children by the product rule.
\vspace{5ex}

\problem{2}{5}{
Write a closed-form expression for 
$\displaystyle \sum_{i=0}^n {n \choose i}$
}

This summation adds for each $i$ the number of ways to choose exactly
$i$ bits to be 1 in an $n$-bit string.  The total is the number of
ways to choose any number of bits to be 1 in an $n$-bit string, which
is the same as the number of $n$-bit strings, $2^{n}$.
\vspace{5ex}

\problem{3}{10}{
What is the definition of independent events?
}

Two events $X$ and $Y$ are independent if and only if
the joint probability is the product of their probabilities,
or $Pr(X \cap Y) = Pr(X) Pr(Y)$.   This
is equivalent to saying that $Pr(X | Y) = Pr(X)$  
{\bf or} that $Pr(Y | X) = Pr(Y)$.
\vspace{5ex}

\problem{4}{10}{
The {\em parity} of a bit vector is the mod-$2$ sum of the number of 
ones in the vector. How many bit-vectors are there of size $n$ that have even
parity?
}

For each bit vector $X$ of length $n-1$, there is exactly one way to
extend it to a bit vector of length $n$ that has even parity---by
adding a 1 if $X$ has odd parity, or by adding a 0 if $X$ has even
parity.  Therefore there are as many even-parity $n$-bit vectors as
there are unconstrained $(n-1)$-bit vectors, $2^{n-1}$.  


\newpage
\wisdom{Reading Solutions.}{This section tests your ability to understand solutions
to previous problems by asking you to solve similar, slightly more complicated
problems.}

\problem{5}{15}
{
You are at point $(0,0,0)$ in three-dimensional space, and you need to 
get to point $(i,j,k)$. You can only make unit-length moves parallel to the
three coordinate axes, and only moves that get you closer to your goal. How
many different paths can you take?
}

No matter how you arrive at $(i,j,k)$, you must have taken $i+j+k$
steps.  Of these steps, $i$ must be along one dimension, $j$ must be
along another, and $k$ must be along the third.  The question becomes
how to distribute the three types of steps amongst the $i+j+k$ total
steps.  There are ${i+j+k}\choose{i}$ ways to choose which of the
$i+j+k$ steps will be along the first dimension, ${j+k}\choose{j}$
ways to choose which of the $j+k$ remaining steps will be along the
second dimension, and ${{k}\choose{k}} = 1$ way to choose which of the
$k$ remaining steps will be along the third dimension.  By the product
rule, the total number of different paths is ${{i+j+k}\choose{i}}
{{j+k}\choose{j}}$.
\vspace{5ex}


\problem{6}{15}{
Consider a town with East-West streets numbered 1 through infinity, and
North-South avenues numbered 1 through infinity.  Suppose you are at 1st
street and 1st avenue, and somewhat inebriated.  You opt not to take a
cab, and instead would like to {\it walk} to your home on $n$th street
and $m$th avenue.  You have forgotten where you live, however, and
every minute you ponder the next movement to make.  With probability
$\frac{1}{2}$ you walk one street forward, and with probability
$\frac{1}{2}$ you walk one avenue forward.  You can only move in the
direction of increasing streets or avenues, and if you miss your house
you're doomed.  If you happen to stumble upon the intersection $(n,m)$
by your house, you recognize it and proceed inside to safety.  What is
the probability that you make it?
}
\vspace{2ex}

You might remember a similar problem from the midterm.
Any path that gets me to $(n,m)$ must require exactly
${n+m-2}$ steps, $n-1$ of which must be in the ``increasing street''
direction and $m-1$ of which must be in the ``increasing avenue''
direction.  There are therefore ${{n+m-2}\choose{n-1}}$ different paths
to my house, since we need only choose which of these steps
are in the ``increasing street'' direction.  Each path
of length ${n+m-2}$ steps has probability $(0.5)^{n+m-2}$,
since at each step we come to some decision that has probability
$0.5$.  Treating each path as a separate event that leads
us to the desired destination, the probability of getting to the
desired intersection is the sum of the probabilities of each
path, ${{n+m-2}\choose{n-1}} (0.5)^{n+m-2}$.

\newpage
\wisdom{Basic Techniques.}{This part will test your ability to apply techniques
for which I have given explicit recipes. If you do not do well on this section,
your study habits could
use adjustment.}

\problem{7}{20}{
The Pittsburgh Pirates, by universal consensus the worst team in the
major leagues, actually have a chance to make the playoffs in October. In order
to do so, they'll need to win at least $90$ of their remaining $150$
games. Assuming the probability that the Pirates will win any single game is
$40\%$, what's the probability that they'll make the playoffs? [A summation
is ok as an answer]
}

We break all the possible winning scenarios into cases based
on how many games the Pirates win in the remainder of the season,
using the sum rule for disjoint events to sum the probabilities
of each case.  This leads to the following summation:

$\sum_{i=90}^{150} {{150}\choose{i}} (0.4)^i (0.6)^{150-i}$.

The first factor of each term in the summation is the number of
win-loss sequences that can result if we enforce that the Pirates win
$i$ of the 150 remaining games.  The rest assigns a probability to
each win-loss sequence having that constraint.  The probability for a
given sequence of wins and losses depends not on the order in which
the wins and losses occur, but only on the total number of each, since
the games are independent events; a win-loss sequence of length 150
with $i$ wins has probability $(0.4)^i (0.6)^{150-i}$ since each win
in the sequence has probability $0.4$ and each loss has probability $1
- 0.4 = 0.6$.

\wisdom{A moment's thought.}{}

\problem{8}{20}
{Let G be a simple graph, i.e., no self loops and at most one edge between any
two nodes. Show that two different nodes of G must have the same degree, i.e., the
same number of neighbors.}

(Clarifications:  We want you to show that {\it there exist}
two distinct nodes in $G$ with the same degree.  Also, limit the 
scope of the statement to graphs with more than 1 vertex.)

Suppose $G$ has $n$ nodes.  Each node is connected to some number of
other vertices (its {\it degree}), a value between $0$ and $n-1$.
There cannot exist a vertex with degree $0$ {\it and} a vertex with
degree $n-1$, because an $n-1$-degree vertex must be connected to
everything, including the loner.  So there are at most $n-1$ distinct
values that the $n$ vertex degrees can take on.  By the pigeonhole
principle, there exists a value that is the degree for at least two
different vertices.



% magic for a Postscript figure:
%
%\begin{figure}[h]
%\centerline{\psfig{file=,width=}}
%\caption{}
%\end{figure}

%\setlength{bigskipamount}{3in}

\section*{Graph theory}
\begin{problems}

\item
Call a vertex of a graph {\em odd} if its degree is odd, and {\em
even} if its degree is even.  Show that the number of odd vertices is
even.

This was covered in recitation.  The basic idea is that the sum of the
degree of each vertex is even.  Split the vertices into two sets: those
with even degree, and those with odd degree.  The sum of the degree
of the vertices with even degree is even, and the overall sum is
even, therefore the sum of the degrees of the vertices with
odd degree is even, which means that there must be an even number of them.

\item
A mouse intends to eat a $3 \times 3 \times 3$ cube of cheese.  Being
tidy-minded, it begins at a corner and eats the whole of a $1 \times 1
\times 1$ cube before going on to an adjacent one.  Can the mouse end in 
the center of the cube?  Why or why not?

No, the mouse cannot.  Color the middle cube black, and also all of the
$1 \times 1 \times 1$ cubes that reside in the middle of one of the
edges of the overall cube.  Color the remainer of the cubes white.
The mouse must alternate eating white and black colored cubes.  Assume
the mouse can finish in the middle.  We
know that the mouse would have to end on a black cube if it ends in
the middle, so pair each black cube eaten with the previous cube
eaten (which must be white), so the mouse ate the same number of
white cubes as black cubes (we know the mouse started on a white
cube, since all of the corner cubes are white).  However, there are
14 white cubes and only 13 black cubes, so at least one white cube
was not consumed.

\item
A {\em forest} is a graph containing no cycles, but not necessarily
connected.  Show that if $F=(V,E)$ is a forest with $c$ components,
then \[|E|=|V|-c\]

Also covered in recitation.  Basically, sum the edges and vertices
for each compenent obtains the result (let $e_i$ and $v_i$ denote
the number of edges and vertices in the i-th component):
$$
\|E\| = \sum e_i = \sum (v_i - 1) = (\sum v_i) - c = \|V\| - c
$$

\item
The usual set of dominos may be represented by the symbol $[ x | y ]$
where $x$ and $y$ are members of the set $\{0,1,2,3,4,5,6\}$.  The
numbers $x$ and $y$ may be equal.  Suppose the rules of the game
require that the dominos be placed in a line so that adjacent dominos
have matching numbers: $[ x | y ]$ is next to $[ y | z ]$, and so
on.  Note that the dominoes $[ x | y ]$ and $[ y | x ]$ are considered
the same dominoe.
\begin{enumerate}
\item
How many different dominoes are there?  Explain your answer.

There are ${7 \choose 2} + 7 = 28$ dominoes.  There are $7 \choose 2$
dominoes with different $x$ and $y$, and 7 where $x = y$.

\item
Show that it is possible to have a {\em complete game}, a game in
which all the dominos are used.  Hint: regard the dominos for which $x
\neq y$ as the edges of the complete graph $K_7$.

Consider $K_7$ labeled with $\{0,1,\ldots,6\}$.  Now, each vertex
has even degree, so there exists a Eulerian tour.  This path is
a sequence of edges.  For each edge, map it to the dominoes with
values equal to the labels on its end-points.  Consider that sequence
of dominoes, where the dominoe $[ x | x ]$ is added whenever $x$
appears first as a dominoe side.  This sequence represents a complete
game.

\item
Calculate the number of complete games of dominos.

wing the logic of the previous part, the placement of nondoubled
dominos in a complete game corresponds to an Euler tour of $K_7$.  How
many Euler tours does $K_7$ have?  First, choose a starting vertex (7
choices).  Initially, you have 6 outgoing edges to choose from, but
the next time you return to this vertex, you'll have only 4 unused
edges, and the third time, only 2 edges.  Thus there are $6 \cdot 4
\cdot 2$ ways to choose how you leave the starting vertex.  For the
other vertices the calculation is slightly different, because they are
initially reached by an edge.  Thus a non-starting vertex choose from
5 outgoing edges on its first visit, 3 on its second visit, and 1 on
its third visit, giving $5 \cdot 3$ choices.  Taking the product of
these choices over all vertices\footnote{You may question this
application of the Product Rule -- doesn't the set of vertex $i$'s
remaining permitted edges depend on the choices that other vertices
have already made?  So how can we blithely multiply vertex $i$'s
choices by vertex $j$'s choices, if they seem dependent?  Yes, the set
of permissible remaining edges may vary depending other vertices'
choices, but the {\em size} of the set is always the same!  So we're
safe.} gives the number of Euler tours on $K_7$ as \[7(6 \cdot 4 \cdot
2)(5 \cdot 3)^6\]

So we have this many ways to place the nondoubled dominos.  To place
each doubled domino somewhere among the nondoubled dominos, observe
that every vertex occurs 3 times in the Euler tour, except the
starting vertex which occurs 4 times.  Each visit in the Euler tour
corresponds to a place in the nondoubled dominos where a doubled
domino can be inserted.  Thus the doubled domino matching the starting
vertex has 4 choices, and the other 6 doubled dominos have 3 choices,
giving a grand total of \[7(6 \cdot 4 \cdot 2)(5 \cdot 3)^6(4\cdot 3^6) \approx 1.11 \times 10^{13} \mbox{ complete games} \]

\end{enumerate}

\item 
Suppose you have a set of $n$ different (labeled) vertices.

\begin{enumerate}
\item
How many complete graphs are there on $n$ vertices?

one

\item
How many paths are there in a complete graph?

Recall that a path is a sequence of vertices (from one to $n$
vertices) with no cycles.  Since order matters, for each path length
$i$ ($1 \leq i \leq n$), we choose an $i$-permutation of the $n$ vertices, which
 can be done $n! \over (n-i)!$.  Summing over all path lengths gives
 \[\sum_{i=1}^{n} {n! \over (n-i)!}\]


\item
How many simple cycles are there in a complete graph?  (Recall that a
simple cycle is a path that starts and ends at the same vertex.)

Let's count cycles of length $i$, then sum for $i = 3, 4, \ldots, n.
(Usually we don't consider a cycle to be simple unless it contains at
least three vertices, and no vertex appears more than once.)  To count
the number of cycles with exactly $i$ vertices, there are $n \choose
i$ choices for the $i$ vertices in the cycle, $i!$ ways of ordering
$i$ vertices, but each cycle is actually being overcounted by a factor
of $i$ (since any vertex could be the start vertex), and 2 because a
cycle is counted once for each possible direction of traversal. (It
would also be reasonable not to divide by 2, since it makes sense to
specify a direction for a cycle, e.g., if the graph is directed.)  Summing over all possible values of $i$ gives the answer:
$$\sum_{i=3}^{n} {{n \choose i} (i-1)! \over 2}$$

\item
How many graphs are there on $n$ vertices?

$2^{n \choose 2}$.  For each possible edge, we choose whether it's
in the graph or not.


\end{enumerate}

\item
Let $G$ be a planar graph with $e$ edges and $f$ faces, such that every
face has at least $k$ sides.

\begin{enumerate}
\item Show that $f \leq 2e/k$.

Suppose you walk around each face counting edges.  Since each edge
butts against exactly two faces, you count exactly $2e$ edges.
However, since every face has at least $k$ sides, you will count at
least $fk$ edges.  Thus $2e \geq fk$, which leads immediately to the
result.


\item Use this fact to show that $K_{3,3}$ is nonplanar.

Suppose you could draw $K_{3,3}$ in the plane.  Every face has a cycle
(the edges surrounding it).  However, it's easy to see that every
cycle in $K_{3,3}$ has at least 4 edges -- cycles must have at least 3
edges in any case, but you need an even-length cycle to get back to
the half of the graph you started in.  Thus every face of the
putatively planar $K_{3,3}$ must have at least 4 sides.  Since $e=9$,
we must have $f leq 4$.  According to Euler's formula $n - e + f = 2$,
however, we must have $f=5$.  So $K_{3,3}$ is nonplanar, by
contradiction.


\end{enumerate}

\end{problems}

\section*{Counting and Probability}
\begin{problems}

\item 
Among the set of digits $\{1,2,3,4,5\}$, first one digit is chosen uniformly at
random, and then another. What's the probability that an odd digit is picked
the second time?

$3/5$, by linearity of expectation.

\item
Say you draw uniformly at random from the elements of the group $S_n$, the
group of permutations on $n$ elements. What's the probability that in the
permutation you elect, the $k$th element will be in the $i$th position?

$$\frac{(n-1)!}{n!}=1/n$$


\item 
What's the probability that among $k$ random digits, $0$ doesn't appear?

$9^k/10^k$



\item
A box contains $90$ good and $10$ defective screws. What's the probability that
if $10$ screws are used, none will be defective?

$$\frac{{{{90}\choose {10}}}}{{{100}\choose{10}}}$$



\item 
Eight eligible bachelors and seven beautiful models have purchased seats in a
$15$-seat row of a theatre. What's the expected number of adjacent seats
ticketed for marriageable couples?

Introduce
\[ x_i = \left\{ \begin{array}{ll}
     1 & \mbox{if seat $i-1$ and $i$ are occupied by people of opposite sex}\\
     0 & \mbox{otherwise}
    \end{array}
    \right. \]

What we're after is $E[x_2 + x_3 + \ldots x_{15}]$. By linearity of expectation,
this is $E[x_2] + E[x_3] + \ldots E[x_15]$. Now let's consider $E[x_j]$ for
some $j$. Well,

$$E[x_j] = 1 \cdot p(x_j=1) + 0 \cdot p(x_j=0) = p(x_j=1)$$

We still need to compute $p(x_j=1)$. The probability that seat $j-1$ has a male
in it is $8/15$. Given this, the probability that the $j$th seat has a female
in it is $7/14$. So the probability of male-female in these two seats is
$(8/15)(7/14)$. By a similar argument, the probability of female-male in these
two seats is $(7/15)(8/14)$. Adding these together gives $8/15$, the
probability that seat $j-1$ and $j$ are occupied by people of opposite
sex. This holds for all $j$.

So we have $E[x_j]=8/15$, and the answer is then $E[x_2] + E[x_3] + \ldots
E[x_15]=14 (8/15)$.



\item
What is $213729^{1018} \pmod{20}$?

By the modular exponentiation rule we learned in Lecture 29, we know that
\[x^{\varphi(n)} = 1 \pmod{n}\]

Recall that $\varphi(n)$, ``the Euler phi function,'' is the number of
integers less than $n$ that are relatively prime to $n$.  For
instance, $\varphi(4)=2$ (only 1 and 3 are relatively prime to 4), and
$\varphi(5) = 4$ (since all integers less than a prime are relatively
prime to it).  Furthermore, we showed in Lecture 29 that if $p$ and
$q$ are relatively prime, then $\varphi(pq)=\varphi(p)\varphi(q)$.
Since 4 and 5 are relatively prime, $\varphi(20) =
\varphi(4)\varphi(5) = 8$.

So we can simplify the problem tremendously:
\begin{eqnarray*}
213729^{1018} \pmod{20}  & = & (213729 \bmod 20)^{1018 \bmod 8} \pmod{20} \\
 & = & 9^2 \pmod{20} \\
 & = & 1
\end{eqnarray*}

\end{problems}

\section*{A Moment's Thought}

\begin{problems}

\item 
What is the expected number of simple cycles in a random graph
drawn on $n$ labeled vertices with edge probability $p$? 

A simple cycle can have between 3 vertices and $n$ vertices.  To
choose a cycle, we first choose its size $i$; then a selection of $i$
vertices to involve in the cycle; and then a way of cyclically
connecting the chosen vertices (see the derivation for the number of
simple cycles on $n$ labeled nodes, above.)  Each possible size-$i$ cycle
exists with probability $p^i$.  The desired expectation is therefore

\begin{eqnarray*}
\sum_{i=3}^{n} {n \choose i} \frac{(i-1)!}{2} p^i
\end{eqnarray*}


\end{problems}

\end{document}

\end{document}
