\documentstyle[12pt]{cmu-art}
%\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 
Steven Rudich}
\vskip 0.1in
\hbox to \hsize{\ \ \ QUIZ 2 \hfil April 16, 1997}
}}}

\noindent
{\bf NAME :} Solution Set\\ \\
{\bf ANDREW ID :} \\ \\
{\bf SECTION :  \ \ A \ \ B \ \ C} \\

\ \\

\noindent
{\bf INSTRUCTIONS. For the first 7 problems you do not need to give any reason
or justification for your answer. For the last two problems you must give
complete explanations. WRITE CLEARLY. WRITE YOUR NAME, ID, and SECTION above.


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

\newpage

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

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


\newpage

\wisdom{EXTRA CREDIT}{Warning: this is a {\bf trick} question.}

\problem{9}{20}{
Let $\Sigma = \{ a , b \}$. Let $S$ be the following set:
\[ \{ XY\ | \ X \in {\Sigma}^{*} ,  Y \in {\Sigma}^{*}, \mbox{ and the number
of a's in X equals the number of b's in Y} \} \]

Prove or disprove that $S$ is regular, i.e., can be accepted by some
finite automaton.
}

$S$ is regular, because it is precisely $\Sigma^{*}$, the set of
all finite strings over $\Sigma = \{ a , b \}$.  The finite automaton
consisting of one state (starting and accepting) with self-loops
on both symbols $a$ and $b$ would accept this language. 

To prove this, we must show that any string $Z$ is in $S$, {\it i.e.}
is of the form $\{ XY\ | \ X \in {\Sigma}^{*} , Y \in {\Sigma}^{*},
\mbox{ and the number of $a$'s in X equals the number of $b$'s in Y}
\} $.  Equivalently, we must show that for every string $Z$ there is a
place where we can split the string in two, such that the left piece
has as many $a$'s as the right piece has $b$'s.

We will prove this by induction on the length $n$ of an arbitrary
string $Z$.  There is one string of length zero, the null string, and
trivially we can split this into two concatenated null strings that
satisfy the desired constraints.  Suppose the property holds for all
strings of length $n$, and consider an arbitrary string $Z$ of length
$n+1$.  $Z$ can be written $CXY$, where $C \in \{a,b\}$ and the
remainder is a string of length $n$, which by the inductive hypothesis
can be split into strings $X$ and $Y$ with as many $a$'s in $X$ as
there are $b$'s in $Y$.  If $C = b$, then the strings $X' = CX$ and
$Y' = Y$ satisfy the desired splitting constraint, and so $Z = X' Y'
\in S$.  If $C = a$, then consider the character $x$ appearing before
$Y$ in $Z = CXY$. ($x$ is well-defined, since even if $X$ is null,
$C$ cannot be.  Let $W = CX - x$, {\it i.e.} the truncation of $CX$ by
one character.)  Regardless of $x$, $xY$ has as many $b$'s 
as $W$ has $a$'s, and so we can write $X' = W$ and $Y' = xY$ to
satisfy the desired splitting constraint, again showing that
$Z = X' Y' \in S$.

An alternate, and perhaps simpler way of proving that $Z \in S$ for
all $Z$ resembles the ``necklace'' extra credit from homework 4.
Consider an arbitrary string $Z$.  Define $f(i)$, where $i$ is an
integer index of a possible splitting point in $Z$, to be the number
of $b$'s after index $i$ {\it minus} the number of $a$'s before index
$i$.  $f(0)$ is the number of $b$'s in the string, and $f(|Z|)$ is
negative the number of $a$'s in the string.  Since $f(i+1)$ and $f(i)$
differ by at most one for all $i$, and since $f$ goes from a positive
number to a negative number in scanning $Z$, there must be some $i'$
such that $f(i') = 0$.  At splitting point $i'$ we satisfy the desired
constraint, showing that $Z \in S$.

\end{document}
