\documentclass[11pt]{article}
\usepackage{amsmath}
\input{macros-course}

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

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1}

\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{\intersect}{\cap}
\newcommand{\union}{\cup}
\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{\fins}{\mathcal{F}}


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

\handout{q1sol}{Quiz 1 Solutions DRAFT 10/6 10:30pm}{October 9, 1999}
%\handout{q1}{Quiz 1 DRAFT 10/6 10:30pm}{October 7, 1999}

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

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{lllll}
Yana Ageeva & Victor Boyko & Mary DeSouza & Sarfraz Khurshid & Mike Leonida\\
Ryan McCullough & Albert Meyer & Alantha Newman & Kyle Rose
\end{tabular}
\end{center}

\medskip

\begin{closeitemize}
\item This quiz is CLOSED book.  There are five (5) problems totaling 100
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.

\iffalse
\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}.
\fi

\item GOOD LUCK!
\end{closeitemize}

\bigskip

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

\medskip
\fi

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

\begin{problems}

\problem\pts{20} We ask you to construct some logical formulas using only
propositional formulas and quantification of variables which range over
just one domain of discourse, $D$, starting from formulas only of the forms
$x=y$ and $P(x,y)$.  Here $x$ and $y$ may be replaced by any variables, but
$P$ is a fixed symbol.

\bparts

\ppart\pts{10} An interpretation for the binary predicate symbol $P$ may be
any binary relation on $D$.  Write a formula whose meaning is that the
interpretation of $P$ is an equivalence relation on $D$.

\solution{

$\forall x P(x,x) \wedge \forall x\forall y (P(x,y) \implies P(y,x))
 \wedge \forall x\forall y \forall z[(P(x,y) \wedge P(y,z)) \implies
P(x,z)]$.
}

\vskip2in

\ppart\pts{10} We can use any simple graph, $G$, to interpret a formula by
letting $D$ be the set of vertices of $G$ and letting $P(x,y)$ mean there
is an edge between $x$ and $y$.  For example, the formula
\[
\forall x \forall y P(x,y)
\]
is true exactly when $G$ is a complete graph.  On the
other hand, the formula
\[
\exists x \exists y (P(x,y) \wedge \neg P(y,x))
\]
is not true for \emph{any} simple graph because in simple graphs edges are
undirected, so an edge between $x$ and $y$ is also and edge between $y$ and
$x$.

Write a formula which is not true for any \emph{two-colorable} graph, but
is true for some simple graph.  (Two-colorable graphs the same as bipartite
graphs.)  Briefly explain why your formula has this property.

\solution{

Say that the graph has a three cycle.  This is satisfied by any graph with
such a cycle, but a three cycle prevents two-colorability.
\[
\begin{array}{lr}
\exists x,y,z(\neg(x=y \vee x =z \vee y=z) & \mbox{$x, y$ and $z$ are three
different vertices}\\
\wedge P(x,y) \wedge P(y,z) \wedge P(z,x)). & \mbox{they form a 3-cycle}
\end{array}
\]
}

\vfill
\eparts

\newpage

\problem\pts{15}  \textbf{Modular Arithmetic and GCD's}

Why can't you find an integer $x$ for which
\[
679\cdot x \equiv 1 \pmod{48015}?
\]

\solution{

$679 \cdot x \equiv 1 \pmod{48015}$ iff $679 \cdot x + 48015 \cdot y = 1$
for some integer $y$.  This is equivalent to having $\gcd(679,48015) = 1$,
but by Euclid's algorithm, $\gcd(679,48015) = \gcd(485,679) =
\gcd(194,485)= \gcd(97,194) = 97 \neq 1$.

}

\newpage

\problem\pts{20} \textbf{Pigeon Hole Principle}

%The Theory of numbers by Niven..., page 208

Let \emph{pigeons} be any set of $2n+1$ integers selected from $1, 2,
\dots, 3n$.

\bparts

\ppart\pts{10} Prove that there must be three consecutive integers that
are pigeons.

\solution{

Let the $n$ successive triples of consecutive integers
$(1,2,3),(4,5,6),(7,8,9) \dots (3n-2,3n-1,3n)$ be the holes.  Assign each
pigeon to the hole in which it occurs.  Since there are more than twice as
many pigeons as holes, three pigeons must occupy one hole, say
$(k,k+1,k+2)$.  These are three consecutive pigeons.

}

\vskip3in

\ppart\pts{10} Conclude that among any set of $2n+1$ integers selected from
$1, 2, \dots, 3n$, there must be two that are relatively prime and one of
these two is divisible by three.

\solution{

Of any three consecutive integers $(k,k+1,k+2)$, one must be divisible by
three.  Say it is either $k$ or $k+1$.  Now there are no common divisors of
$k$ and $k+1$, because if $k+1$ was divided by any divisor of $k$ there
would be a remainder of 1.  So in this case, $k$ and $k+1$ are the desired
two relatively prime pigeons, and one of them is divisible by three.  If
neither $k$ nor $k+1$ is divisible by three, then $k+2$ must be divisible
by three, so in this case, by the same reasoning, $k+1$ and $k+2$ will be
the desired two pigeons.

}


\iffalse

\ppart\pts{10} Consider sequence of integers $n_1, n_2, \dots, n_k$, where
$k\geq 1$.  Show that there is subsequence of consecutive elements from
this sequence whose sum is divisible by $k$.

\solution{ First look at the $k$ sums $n_1, n_1+n_2, n_1+n_2+n_3,
n_1+n_2+\ldots +n_k$.  If one of these is divisible by $k$, we are done.
If not, each of these is nozero modulo $k$.  There are only $k-1$ nonzero
numbers mod $k$, so by the pigeonhole principle, two of these sums must by
congruent mod $k$, and their difference is congruent to zero mod $k$, that
is, it is divisible by $k$

In that case, suppose $n_1+n_2+\ldots+n_l~\mbox{and}~n_1+n_2+\ldots+n_m$
are the sums in the question and $l>m$.  Then $n_{m+1}+n_{m+2}+\ldots+n_l$
is the desired subsequence of elements.
}
\fi


\vfill

\eparts

\newpage

\problem\pts{20}   \textbf{Infinite cardinality}

For each of the following sets, state whether it is countable or not, and
prove your statement.

\bparts

\ppart\pts{5} The set of all prime numbers.

\solution{

The natural numbers, $\naturals$, are countable by definition, and any
subset of a countable set is countable.  So the set of primes is countable
because it is a subset of $\naturals$.

}

\vskip2in

\ppart\pts{5} The set of all sets whose only members are prime numbers.

\solution{

This set is uncountable, because it is the powerset of the set of primes.
But since there are an infinite countable number of primes, we know
$\mbox{primes} \bij \naturals$, so $P(\mbox{primes}) \bij P(\naturals)$,
and by Cantor's Theorem, $P(\naturals)$ is uncountable.

Alternatively, this could be proved by repeating Cantor's diagonal argument
with the set of primes in place of $\naturals$.}

\vskip2in

\ppart\pts{10} The set of all finite sets consisting of a prime number of
primes.  (For example, $\set{7,11,13}$ is such a set, but
$\set{7,11,13,17}$ is not because its size is not a prime, and
$\set{7,11,13,17,18}$ is not such a set because one of its members is not
prime.)

\solution{

Let $S_n$ be the set of nonempty subsets of $\naturals$ with maximum
element $n$.  $S_n$ is finite---it has $2^{n}$ elements---and therefore
certainly is countable.  Hence, the set $\fins \eqdef \union_{n \in
\naturals} S_n$ is a countable union of countable sets, and therefore is
also countable.  But $\fins$ is the set of \emph{all} nonempty finite
subsets of $\naturals$, so the set of prime-size sets of primes is a subset
of $\fins$, and therefore is also countable.

}

 \vfill

\eparts

\newpage

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

A \emph{rooted, ordered tree} has a designated root node and a sequence of
subtrees that branch off the root node.  Each of the subtrees is another
rooted, ordered tree.  Some examples of rooted, ordered trees, $\ROT$ for
short, appear in the attached Figure.  (Trees are conventionally drawn
upside-down: the root is at the top.)

Rooted trees can be neatly formalized by abstracting a tree to be
\emph{the same} as the ordered sequence of its subtrees.  Formally, a tree
with $n$ subtrees $T_1,\dots,T_n$ is simply defined to be the $n$-tuple
$(T_1,\dots,T_n)$.  We allow $n=0$, so a leaf with no subtrees is a
\emph{$0$-tuple}, denoted as $\nil$.

Now we can formulate a simple recursive definition of $\ROT$, as follows:
\begin{itemize}
\item $\nil$ is an element of the set \ROT.

\item If $T_1,\dots,T_n$ is a sequence of $n>0$ elements in \ROT, then the $n$-tuple
$(T_1,\dots,T_n)$ is an element of \ROT.

\end{itemize}

The \emph{size} of a tree is the number of nodes in it (including leaf
nodes).

\bparts

\ppart\pts{3}   Give a recursive definition of $\sz(T)$ for $T \in \ROT$.

\solution{

\begin{eqnarray*}
\sz(\nil)            & \eqdef & 1,\\
\sz((T_1,\dots,T_n)) & \eqdef & 1 + \sum_{i=1}^n \sz(T_i).
\end{eqnarray*}
}

\vskip2in

\eparts

\emph{Full binary trees}, $\FBT$, are the special case of $\ROT$ in which
every node is a leaf or has \emph{exactly two} subtrees, as illustrated in
the Figure.  Formally, $\FBT$ has the same recursive definition as $\ROT$
except $n$ is always 2 in the second clause of the definition.

Although full binary trees are a special case of rooted ordered trees,
there is a standard way to represent an arbitrary tree in $\ROT$ as a full
binary tree.  Some examples are shown in the Figure.  We define $\brep$ to
be the function that maps any rooted, ordered tree to its representation as
a full binary tree.  Conversely, the function $\unrep$ maps any full binary
tree to the rooted tree in $\ROT$ that it represents.

To give the mathematical definitions of $\brep$ and $\unrep$, we first
define the \emph{\cons} function on tuples as follows:
\begin{eqnarray*}
\cons(t,\nil) &\eqdef & (t),\\
\cons(t_0,(t_1,\dots,t_n)) & \eqdef & (t_0,t_1,\dots,t_n),
\end{eqnarray*}
for $n \geq 1$.

\newpage

\bparts

\ppart\pts{3}  Prove that
\[
\sz(\cons(T_1,T_2)) = \sz(T_1) + \sz(T_2).
\]
for all $T_1,T_2 \in \ROT$.

\solution{There are two cases:
\begin{enumerate}

\item If $T_2 = \nil$, then
\[
\begin{array}{rclr}
\sz(\cons(T_1,\nil)) & = & \sz((T_1)) & \mbox{by def of \cons}\\
   & = & 1 + \sz(T_1) & \mbox{by 2nd clause of def of \sz}\\
   & = & \sz(\nil) + \sz(T_1) & \mbox{by 1st clause of def of \sz}\\
   & = & \sz(T_1) + \sz(T_2).
\end{array}
\]

\item: Otherwise $T_2 = (T_3,T_4)$ for some $T_3,T_4 \in \ROT$, and
\[
\begin{array}{rclr}
\sz(\cons(T_1,(T_3,T_4))) & = & \sz((T_1,T_3,T_4)) & \mbox{by def of \cons}\\
   & = & 1 + \sz(T_1) + \sz(T_3) + \sz(T_4) & \mbox{by 2nd clause of def of \sz}\\
   & = & \sz(T_1) + (1+ \sz(T_3) + \sz(T_4))\\
   & = & \sz(T_1) + \sz((T_3,T_4))  & \mbox{by 1st clause of def of \sz}\\
   & = & \sz(T_1) + \sz(T_2).
\end{array}
\]

\end{enumerate}

Notice that there was no need for induction in the proof.

}

\vskip4in
\eparts

The function $\unrep$ can now be defined recursively as follows:

\begin{itemize}
\item $\unrep(\nil) \eqdef \nil$.

\item If $B_1,B_2 \in \FBT$, then
\[
\unrep((B_1,B_2)) \eqdef \cons(\unrep(B_1), \unrep(B_2)).
\]
\end{itemize}

\newpage

\bparts

\ppart\pts{9} Prove that if $B \in \FBT$, then $\sz(\unrep(B)) = (\sz(B)+1)/2$.

\solution{

The proof is by structural induction on the definition of \FBT.  The
induction hypothesis is $P(B) \eqdef [\sz(\unrep(B)) = (\sz(B)+1)/2]$.

\begin{proof}
\textbf{base case} $B = \nil$: $P(B)$ holds because $\unrep(B) = \nil \in \ROT$ and
$\sz(\unrep(B)) = 1 = 2/2 = (\sz(B)+1)/2$.

\textbf{induction case} $B = (B_1,B_2)$ for some $B_1,B_2 \in
\FBT$ such that $P(B_1)$ and $P(B_2)$ hold.
We must prove $P(B)$.


Now
\[
\begin{array}{rclr}
 \sz(\unrep(B)) & = & \sz(\unrep((B_1,B_2)))\\
    & = & \sz(\cons(\unrep(B_1), \unrep(B_2))) & \mbox{by def of $\unrep$}\\
    & = & \sz(\unrep(B_1)) + \sz(\unrep(B_2)) &  \mbox{by $\sz(\cons(,))$
                   given above}\\
    & = & (\sz(B_1)+1)/2 + (\sz(B_2)+1)/2 & \mbox{by $P(B_1)$ and $P(B_2)$}\\
    & = & (\sz(B_1)+1 + \sz(B_2)+1)/2\\
    & = & ((1+ \sz(B_1) + \sz(B_2)) +1)/2\\
    & = & (\sz((B_1,B_2)) +1)/2 & \mbox{by def of $\sz((B_1,B_2)$}\\
    & = & (\sz(B) + 1)/2.
\end{array}
\]
\end{proof}
}

\eparts

\newpage
 
The correspondence between $B \in \FBT$ and the tree in \ROT\ which it
represents is exact.  A precise way to say this is that the
functions $\brep$ and $\unrep$ have the properties
\[
\unrep(\brep(T)) = T
\]
for all $T \in \ROT$, and
\[
\brep(\unrep(B)) = B
\]
for all $B \in \FBT$.

\bparts

\ppart\pts{5} Give a recursive definition of the function $\brep:\ROT \to
\FBT$ (Just give the definition---you do not need to prove that it has the
property above.)


\solution{
\begin{itemize}
\item $\brep(\nil) \eqdef \nil$.

\item $\brep((T_1)) \eqdef (\brep(T_1),\nil)$.

\item For, $n \geq 2$,
\[
\brep((T_1,T_2,\dots, T_n)) \eqdef \cons(\brep(T_1),\brep((T_2,\dots,T_n))).
\]

\end{itemize}
}

\vskip2.2in

\ppart\pts{5} Conclude that for all $n>0$, there are the same number of rooted,
ordered trees of size $n$ as there are full binary trees of size $2n-1$.

\solution{

If $\sz(T)=n$ then $n= \sz(\unrep(\brep(T))) = (\sz(\brep(T))+1)/2$, so
$\sz(\brep(T)) = 2\sz(T)-1 = 2n-1$.  Conversely, we know that if $\sz(B) =
2n-1$, then $\sz(\unrep(B)) = ((2n-1)+1)/2 = n$.  So $\brep$ defines a
function from rooted ordered trees of size $n$ to full binary trees of size
$2n-1$, and the existence of $\unrep$ impies that $\brep$ defines a
bijection between these sets, so they are the same size.  }

\vfill

\eparts


\end{problems}

\end{document}
