\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 Maggs-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?
}
 
\vspace{10ex}

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

\vspace{10ex}

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

\vspace{10ex}

\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?
}

\vspace{10ex}


\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?
}

\vspace{25ex}


\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}

\vspace{25ex}

\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]
}

\vspace{30ex}

\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.)

\vspace{15ex}



% 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.

\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?

\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\]

\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.
\begin{enumerate}
\item
How many different dominoes are there?  Explain your answer.

\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$.

\item
Calculate the number of complete games of dominos.
\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?

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

\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.)

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

\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$.

\item Use this fact to show that $K_{3,3}$ is nonplanar.
\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?

\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?

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

%\item 
%$n$ balls are placed randomly into $n$ cells. What's the probability that
%exactly one cell remains empty? 

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

\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?

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

\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$? 

%
% This problem is too messy as it's specified here.
% It might be better if each goornk reproduces only once, then
% hops up to the top.
%
%\item
%Goornks reproduce asexually on staircase steps.  On every step it
%hits, a Goornk (of either type) produces a {\it weak} goornk, which
%promptly hops up to the next step, and a {\it strong} goornk, which
%hops up two steps at once, bypassing the step in between.  How many
%goornks will eventually arrive at the top of a staircase with $k$
%steps if a single goornk reproduces at the bottom?

\end{document}

\end{document}
