\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\input{macros-course}


\querysol{q1}{Quiz 1}{Match 8 2000}{q1sol}{Quiz 1 Solutions}{Match 15 2000}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\pts}[1]{\relax[#1 pts]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\begin{document}

\titlebar

\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{lllll}
\end{tabular}
\end{center}

\medskip

\begin{closeitemize}
\item This quiz is open book.  There are XXX problems totaling XXX
points.  Problem parts are labelled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{these pages
may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  Please
keep your entire answer to a problem on that problem's page.

\item You may assume any of the results from class or notes in any proofs
you give.

\item Show your work, as partial credit will be given.  You will be
  graded not only on the correctness of your answer, but also on the
  clarity with which you express it.  {\bf Be neat and write legibly}.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\noindent Write the hour at which your Friday recitation begins \brule{3em}

\medskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  20 & & \\ & & & \\\hline & & &\\
2 &  15 & & \\ & & & \\\hline & & &\\
3 &  20 & & \\ & & & \\\hline & & &\\
4 &  20 & & \\ & & & \\\hline & & &\\
5 &  25 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 100 & & \\
& & &\\
\hline
\end{tabular}
\end{center}


\newpage

\begin{problems}

\problem\pts{}  \textbf{Logic}

It is time to take pictures at Richard Nixon Elementary School.  In
Mrs. Tjaded's class are six students: Carl, David, Josh, Kyle, Rob,
and Shishir.  Naturally, the students are arguing, so in order to
minimize the disruption on the waiting line, Mrs. Tjaded has to order
the students according to the following rules:

\begin{enumerate}
\item\label{hs:r1} Carl must come before Josh.
\item\label{hs:r2} David must be directly in front of or directly
  behind Kyle
\item\label{hs:r3} Shishir must be the fifth person on line.
\item\label{hs:r4} Josh cannot be last.
\end{enumerate}

\bparts

\ppart Which of the following people could be last on line?  Explain
your reasoning.

\begin{enumerate}
\item[(1)] Shishir
\item[(2)] Kyle
\item[(3)] Rob
\item[(4)] Carl
\item[(5)] David
\end{enumerate}

\solution{(1) is wrong because it violates rule \ref{hs:r1}.  (2) and
  (5) are wrong because if one of Kyle or David are sixth in line, the
  other cannot be fifth (since Shishir is there).  (4) is wrong
  because Josh must come after him, so the last place in which Carl
  could be located is fourth.  Rob (3) is the only one of these 5 who
  could be last on line.  }

\ppart Suppose we add the constraint, ``Carl must be second.''  Prove
that there is no way to line up the kids.

\solution{If Carl is second, there is no way to line up David and
Kyle, who must be adjacent.

Clearly, neither Kyle nor David can be first or sixth.  And, since
Josh must come after Carl but cannot be last, Josh must be fourth or
fifth; but then neither Kyle nor David could be fourth or fifth,
because the other would not be adjacent.

Hence, an ordering under these constraints is impossible.}

\eparts


\problem\pts{}  \textbf{Relations}

\begin{problemparts}

  \ppart Let $F(x,t)$ denote ``you can fool person $x$ at time $t$.''
  Write in logical notation ``you can fool all the people some of the
  time, and some of the people all the time, but you can't fool all
  the people all the time.''  Assume ``some of'' means ``at least
  one.''

  \ppart What is the common name for the reflexive closure of the
  ``less than'' relation?

  \ppart What is the common name for the transitive closure of the
  ``child of'' relation?

  \ppart What is the common name for the inverse of the ``child of''
  relation?

  \ppart Consider the partial order ``$aRb$ if $a$ divides $b$ without
  remainder.''  What are the minimal elements of this relation called?

\end{problemparts}



\problem\pts{}  \textbf{State Machines}

Consider the following algorithm on graphs:
%
\begin{center}
\begin{minipage}{5in}
  Consider a graph $G$ in which each vertex is either uncolored, or is
  colored red or blue.  Initially all vertices except one---call this
  vertex $s$---are uncolored, while $s$ is red.

  At each step, one of two events can occur:
  \begin{enumerate}
  \item Choose an uncolored vertex $v$ which is adjacent to a red
    vertex, and color $v$ blue.
  \item Choose an uncolored vertex $v$ which is adjacent to a blue
    vertex, and color $v$ red.
  \end{enumerate}
  If neither rule can be applied, the algorithm halts.  If all
  vertices are colored, it halts in a ``well done'' state; otherwise
  it halts in a ``stuck'' state.
\end{minipage}
\end{center}

\bparts

\ppart Formalize this algorithm as a state machine.

\solution{Number the $n$ vertices of graph $G=(V,E)$ uniquely with the
  integers $1,\ldots,n$.  A state $q$ then consists of an array
  $q.C[1,\ldots,n]$ of color values (red, blue, or uncolored) indexed
  by vertex.
  
  The start states are simply the subset of states $q$ in which
  exactly one entry $q.C[i]=$red while $\forall j\not=i\ 
  q.C[j]=$uncolored.
  
  The termination states are the subset of states in which all entries
  are either red or blue or the ``stuck'' state.

  The transitions are all of the form:
  \begin{eqnarray*}
    (q,q')\in\delta & \iff & \exists i\ q.C[i]=\mathrm{uncolored} \\
      && \wedge \big[\left(q'.C[i]=\mathrm{red}\wedge\exists k\ q.C[k]=\mathrm{blue}\wedge (v_i,v_k)\in E\right) \\
      && \ \ \ \vee \left(q'.C[i]=\mathrm{blue}\wedge\exists k\ q.C[k]=\mathrm{red}\wedge (v_i,v_k)\in E\right)\big] \\
      && \wedge \forall j\not=i\ q.C[j]=q'.C[j]
    \end{eqnarray*}

}

\ppart Prove that the algorithm eventually halts.  

\solution{We prove that there is a decreasing derived variable to show
  termination.  Consider the variable $d$ denoting the number of
  uncolored vertices.  Each step decreases $d$; since $d$ starts at
  $n-1$ and is always $\geq 0$, it must eventually reach $0$,
  whereupon the algorithm terminates.}


\ppart Prove the following fact: on any path connecting a colored
vertex and an uncolored vertex, there must be some edge incident on
both a colored vertex and an uncolored vertex.

\solution{Consider the path $p=v_1v_2\cdots v_k$, of which $v_1$ is
  colored and $v_k$ is uncolored.  Assume there is no edge
  $(v_i,v_{i+1})$ such that $v_i$ is colored and $v_{i+1}$ is
  uncolored.  Then, by induction starting from $v_1$, $v_i$ are
  colored for all $i$, so $v_k$ is colored; this is a contradiction.
  }

\ppart Using the fact you proved in the previous part, prove that if
$G$ is connected, all vertices are colored when the algorithm halts.

\solution{ Say the algorithm halts with some vertex uncolored.  Since
  the graph is connected, there is a path from $v$ to some colored
  vertex $w$.  By the given fact, there must be an edge along this
  path for which one endpoint $x$ is colored and the other $y$ is
  uncolored.  We can apply one of the two steps above, assigning to
  $y$ the opposite of $x$'s color.  Thus, the algorithm should not
  have halted yet.}

\ppart Consider applying this algorithm to \textit{bipartite} graphs,
i.e., graphs in which the vertices can be partitioned into two sets
$R$ and $B$ such that there is no edge between any pair of vertices in
$R$ (and similarly for $B$).  Suppose the initial state has some
vertex in $r$ colored red.  Using the invariant theorem, prove that in
any state, only vertices of $R$ are colored red and only vertices of
$B$ are colored blue.


\solution{
  
  We need to show that the invariant is preserved from one step to the
  next, which we do by induction on the number of colored vertices.
  
  $P(n)=$``After $n$ vertices are colored, all red vertices are in $A$
  and all blue vertices are in $B$.''
  
  \textit{Base case.} In any start state, there is exactly one red
  vertex in $R$---by construction---and no blue vertices.  Therefore,
  $P(1)$.
  
  \textit{Induction.} Assume $P(n)$.  Then, consider an execution in
  which $n+1$ vertices are colored.  Consider the vertex $i$ which was
  colored last.  If we uncolor it, we can apply the induction
  hypothesis and conclude that all red vertices were in $R$ and all
  blue vertices were in $B$.
  
  Now we must prove that vertex $i$ is colored correctly.  Assume WLOG
  that vertex $i$ is in $B$.  For $i$ to have been colored, it must
  have been the case that $i$ was adjacent to a colored vertex; but
  all vertices adjacent to $i$ are in $R$ (by the definition of
  bipartite), so $i$ must have been colored blue.  This satisfies the
  invariant theorem, so $P(n+1)$.
  
  Thus, $\forall n\ P(n)$, so all red vertices are in $R$ and all blue
  vertices are in $B$. 
}

\ppart Combine the previous parts to prove that when run on a
 connected bipartite graph, the above algorithm halts and outputs a
 valid 2-coloring.

\solution{We proved the algorithm halts on connected graphs with all
  vertices colored.  By the invariant above, this means all vertices
  in $R$ are red and all vertices in $B$ are blue.  By the definition
  of bipartite, there exists no pair of like-colored vertices
  connected by an edge, so this is a valid 2-coloring.  }

\eparts

\problem\pts{}  \textbf{Relations}

Burton read the induction proof for the 2-coloring problem from the
second problem set, and ``discovered'' another interesting property.
The original problem was
%
\begin{center}
\begin{minipage}{5in}
Suppose you take a piece of paper and draw a bunch of straight lines,
each in its own arbitrary direction, that completely cross the paper.
This divides the paper up into polygonal regions.  Prove by induction
that you can always color the various regions using only \emph{two}
colors, so that any two regions that share a boundary line are
different colors.  Note that this need not be true of regions that
share only a boundary point.
\end{minipage}
\end{center}
%
Burton defined a relation between regions as follows:
%
\[ xRy ::= x=y\mathrm{,\ or\ region\ }x\textrm{\ does not border region\ }y \]
%
Burton claims $R$ is an equivalence relation.  Is it?  If so, prove
it; if not, provide a counterexample and explain why it is a
counterexample.

\solution{It is not an equivalence relation.  While it is reflexive
  and symmetric, it is not transitive.  Note in figure \ref{fig:regions}
  that $1R2$ and $2R3$ but $\neg(1R3)$.

\begin{figure}[htbp]
\centerline{\psfig{figure=regions.eps,height=1.0in}}
\caption{Regions made from straight lines drawn completely across the outer block.}\label{fig:regions}
\end{figure}
}

\problem\pts{}  \textbf{Induction}

Use induction to prove that
 \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
 whenever $n$ is a natural number.

\solution{
Use induction to prove our proposition, P(n), 
 \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
 whenever $n$ is a natural number.

{\bf Base Case:}  $n = 0 $

The left side is an empty sum, so $0 = \left(\frac{0 \cdot 1}{2}\right)^2 = 0$.

{\bf Inductive Step:}   Show that $P(n)  \rightarrow P(n+1)$.

By the inductive hypothesis, we assume that 
 \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n+1)^3 \\
&= &\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\\
&= &\frac{n^2(n+1)^2 + 4(n+1)(n+1)^2}{4}\\
&= &\frac{(n^2+4n+4)(n+1)^2}{4}\\
&= &\left(\frac{(n+1)(n+2)}{2}\right)^2\\
\end{eqnarray*}

And our hypothesis is proved.
}

\problem\pts{}  \textbf{Induction}

The denizens of the land of Frohike have a passion for masochism:
their currency---the Eebae$^{\textrm{\tiny TM}}$---uses coins only of
values 5, 7, and 11 Eebaes.

The Frohikies have discovered over time that any value of at least 14
Eebaes can be produced using some combination of these coins, but some
values below 14 are not possible.

Prove by induction that all values of at least 14 Eebaes can be made
from these three coin values.

\solution{We wish to prove $P(n)=$``$n=5a+7b+11c$, for some
  $a,b,c\in\naturals$'' for all $n\geq 14$.

  \textit{Base cases.}

  $P(14)=7*2$

  $P(15)=5*3$

  $P(16)=5*1+11*1$

  $P(17)=5*2+7*1$
  
  $P(18)=7*1+11*1$
  
  \textit{Induction.} Fix $N\geq 19$.  Assume $P(n)$ for all $14\leq n\leq
  N$.  Prove $P(N+1)$.
  
  Any number $N+1\geq 19$ can be made by adding $5$ to $N+1-5=N-4$.
  Since we have assumed $P(N-4)$ (by our induction hypothesis),
  $P(N-4)\Rightarrow P(N+1)$.

  By strong induction, $\forall n\geq 14:\ P(n)$.\kpfend
}

\problem\pts{}  \textbf{Structural Induction}

Consider the sets $S_1,S_2,\ldots$ defined inductively as
%
\begin{itemize}
\item $S_0 = \set{0,1}$
\item For all $n\geq 1$, $S_n = \set{\frac{x+y}{2}\ |\ x,y\in S_{n-1}}$
\end{itemize}
%
i.e., where $S_n$ contains the average values of each pair of numbers
in $S_{n-1}$.

\bparts

\ppart Write out the elements of each of the following sets: $S_1$,
$S_2$, and $S_3$.  Generalize (in your own words or in symbols) what
the elements of $S_n$ are.

\solution{
  \begin{center}
    \begin{tabular}{rl}
      $S_1$ & $\set{0,1/2,1}$ \\
      $S_2$ & $\set{0,1/4,1/2,3/4,1}$ \\
      $S_3$ & $\set{0,1/8,1/4,3/8,1/2,5/8,3/4,7/8,1}$
    \end{tabular}
  \end{center}
  
  $S_n$ contains $2^n+1$ elements (including 0 and 1) evenly spaced
  along the unit interval; i.e., $S_n=\set{i/2^n|0\leq i\leq 2^n}$.  }

\ppart Prove by induction that for all $n$, $1/3\not\in S_n$.  You may
not assume your generalization from the previous part is true; you
must prove that statement if you wish to use it.

\solution{Strengthen the theorem to
\[ P(n)=\mathrm{``For\ all\ }a/b\in S_n\mathrm{\ with\ }a,b\in\naturals\mathrm{\ where\ }a/b\mathrm{\ is\ in\ reduced\ form,\ }b=2^k\mathrm{\ for\ some\ }k\mathrm{"} \]
Clearly, if $\forall n\ P(n)$, then $\forall n\ 1/3\not\in S_n$.
Thus, we need only prove $\forall n\ P(n)$.

\textit{Base cases.} $0=0/2^0$, $1=1/2^0$.

\textit{Induction.} Assume $P(n)$.  By the construction of $S_{n+1}$,
all elements of $S_{n+1}$ are of the form $(x+y)/2$ for some $x,y\in
S_n$.  Fix any two such elements $x,y\in S_n$, where (by the induction
hypothesis) $x=a/2^k$ and $y=c/2^\ell$ with $a,b,k,\ell\in\naturals$.

Assume WLOG $k\geq\ell$.  Then,
%
\begin{eqnarray*}
(x+y)/2
& = & (a/2^k + c/2^\ell)/2 \\
& = & (a/2^k + c2^{k-\ell}/2^k)/2 \\
& = & (a + c2^{k-\ell})/2^{k+1}
\end{eqnarray*}
%
While this may not be in reduced form, reduction cannot introduce any
non-2 factors into the denominator, so this fits the form specified by
the theorem.  Therefore, $P(n+1)$.

By induction, $\forall n\ P(n)$.  Thus, $\forall n\ 1/3\not\in
S_n$.\kpfend

}

\eparts

\end{problems}

\end{document}
