\documentstyle[12pt,psfig,epsf]{cmu-art}

\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

%\setlength{\textwidth}{6.50in}
%\addtolength{\oddsidemargin}{-0.75in}
%\addtolength{\evensidemargin}{-0.75in}
%\topmargin -1in
\begin{document}
\centerline{\psfig{figure=tpi.eps,height=1.0in,width=4.0in}}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ QUIZ 2 \hfil Bruce Maggs \hfil March 16, 1998\ \ \ }

\vskip 0.1in
}}}

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

\noindent
{\bf INSTRUCTIONS. For the first 7 problems you do not need to give
any reason or justification for your answers. For the remaining
problems you must give complete explanations. WRITE CLEARLY.  WRITE
YOUR NAME AND ANDREW ID ABOVE AND CIRCLE YOUR SECTION.


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

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

\wisdom{Repeat After Me.}{This part is to test your ability to study 
material that has been pre-digested and labeled as useful or
likely to appear on exams. If you do not do well on this section, your
study habits could use adjustment.}


%
% Questions for the ``Repeat After Me'' section
%

\problem{1}{5}{How many ways are there of seating $n$ people around a circular table?
(Two seatings are considered the same if one is simply a circular
shift of the other.)
}

\problem{2}{5}{True or false: for all sets $A$ and $B$, if $A \subset B$ and $A \neq B$,
then $|A| \neq |B|$.
}
% hburch: finite? No, countably infinite is more interesting

\problem{3}{5}{True or false: the rational numbers are countable.}

\problem{4}{5}{Give a formula for $|A \cup B \cup C|$ in terms of
the intersections of $A$, $B$, and $C$, where $A$, $B$, and $C$ are
finite sets.}


\problem{5}{5}{How many functions are there from the integers in the range
$[1 \ldots k]$ to the boolean values $\{0,1\}$?
}

\problem{6}{5}{
True or false: the problem of 2-coloring a graph is NP-complete.
}

\wisdom{Reading Solutions.}{This section tests your understanding of
the homework assignments, including your ability to read the
homework solutions that we hand out.}

\problem{7}{5}{
How many different poker hands are flushes?
}

\problem{8}{10}{
Using only NAND gates, draw a circuit that computes the EQUALS
function, described in the truth table below.  (You may use
your NAND gate to design other kinds of gates and then use
these gates.)

\begin{tabular}{rr|l}
$x$ & $y$ & $x == y$ \\ \hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\
\end{tabular}
}

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

In order to show that two sets $R$ and $S$ have the same cardinality,
it suffices to find a function $f: R \rightarrow S$ and then {\it
prove\/} that $f$ is both one-to-one and onto.  A function $f$ is
one-to-one if for all $x$ and $y$ in $R$, if $f(x) = f(y)$ then $x =
y$.  A function is onto if for every $s \in S$, there exists an $r \in
R$ such that $f(r) = s$.

\problem{9}{10}{Prove that the set of all even integers has the same cardinality as
the set of all integers that are multiples of three.
}

\problem{10}{10}{Draw a finite automaton that accepts the language of
consisting of all strings of $a$'s and $b$'s that can be formed by
starting with the name of the ``easy listening'' rock group $abba$ and
replacing each $a$ with a non-empty string of $a$'s and each $b$ with
a non-empty string of $b$'s.  Examples of strings in the language
include $abba$, $aaaabba$, and $aaabbbbaaa$.}


\newpage

\wisdom{A Moment's Thought!}
{This section tests your ability to think a little
bit more insightfully. You must give complete explanations of your answers.} 

\problem{11}{15}{Ben Bitdiddle (our favorite misguided 15-299 student)
has just made a remarkable discovery.  He has designed an algorithm
that can factor any number $n$ in time that is polynomial in $n$.  In
fact, his algorithm is so simple that he can explain it to anyone: First
see if $2$ divides $n$, then see if $3$ divides $n$, then see if $4$
divides $n$, and so on.  It takes at most $n-1$ divisions to find all
of the factors of $n$.  Knowing that the most powerful cryptographic
systems rely on the difficulty of factoring, Ben is deeply concerned
about the national security implications of his discovery.  So he
turns to another 15-299 student for advice.  This student tells Ben
that in one minute, with paper and pencil, a man can write out the
digits of a base-10 number that all of the computers in the world
working together for a full year in 1998 could not factor using Ben's
algorithm.  How can this be?}

\newpage

\problem{12}{20}{Prove that the set of complex numbers whose real and
imaginary parts lie in the ranges $[0,1]$ and $[0\cdot i,1 \cdot i]$ has the
same cardinality as the set of real numbers in the range $[0,1]$.

Too help you solve this problem, I will provide a useful lemma.
It's proved on the last page of the quiz, in case you're curious about
the proof.

{\bf Lemma:} {\it The set of real numbers in the range $[0,1]$ can be
placed in one-to-one and onto correspondence with the set of countably
infinite sequences of base-10 digits.}

Hint: Use this lemma to dovetail through the complex numbers.
}


\newpage

{\bf Lemma: }{\it The set of real numbers in the range $[0,1]$ can be
placed in one-to-one and onto correspondence with the set of countably
infinite sequences of base-10 digits.}

{\bf Proof of Lemma:} Any real number can be expressed as a countably
infinite sequence of digits using its base-10 representation.  For
example, $1/3$ can be expressed as $0.3333\ldots$, $1/\sqrt{2}$ as
$0.70710678\ldots$, and $1/2$ as $0.50000\ldots$.  This observation
would give us a one-to-one and onto correspondence between the reals
and the sequences, except for one annoying detail: some real numbers
have two representations!  As an example, $1/2$ can also be expressed
as $0.49999\ldots$.  This detail makes the proof messy, so I'll take
care of it for you.

A real number in $[0,1]$ has two countably infinite representations if
and only if it has a finite representation.  In the previous example,
the finite representation of $1/2$ is 0.5.  The real numbers with
finite representations are all rational, and there are a countably
infinite number of them.  This means that the set of sequences of
base-10 digits that ``share'' a real number with another sequence is
also countably infinite.

To place the reals in the range $[0,1]$ into one-to-one and onto
correspondence with the sequences, we will handle the rationals and
the irrationals separately, as in Question 2 on Assignment 7.  Each
irrational number is placed into correspondence with its base-10
representation.  This mapping is one-to-one and onto.  The set of
rationals is put into one-to-one and onto correspondence with the set
of sequences of base-10 digits that represent one or two rational
numbers -- but now some sequences are in correspondence with rational
numbers that they do not represent, and vice versa.\qed

\end{document}


