\documentstyle[12pt,macpsfig,amssymb]{article}
\input{/a/class/6.042/fall94/handouts/macros-course}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

\setcounter{page}{0}

%\newcommand{\pr}{\problem}
\newcommand{\pr}{\newpage\problem}
\renewcommand{\bparts}{\begin{testproblemparts}}
\renewcommand{\eparts}{\end{testproblemparts}}

\begin{document}

\examinitials{Quiz 1}{October 19, 1994}


\begin{closeitemize}

\item Put your name on the top of each page---the pages of this booklet  
will be separated for grading.

\item This quiz ends at 9 {\sc p.m.} It contains eight problems.  You
have 120 minutes to earn 100 points.

\item This quiz is closed book.  You may use one $8\frac{1}{2}''\times
11''$ handwritten crib sheet.  You may not use a calculator.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  Please do not
put part of the answer to one problem on the back of the sheet for
another problem.

\item Do not spend too much time on any problem.  Read them all
through first and attack them in the order that allows you to make the
most progress.

\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.  Be neat.

\end{closeitemize}

\renewcommand{\arraystretch}{.5}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
1 &  9 & \\ & &\\ \hline	& &\\
2 &  9 & \\& &\\\hline& &\\
3 & 10 & \\& &\\\hline& &\\
4 & 10 & \\& &\\\hline& &\\
5 & 30 & \\& &\\\hline& &\\
6 & 10 & \\& &\\\hline& &\\
7 & 10 & \\& &\\\hline& &\\
8 & 12 & \\& &\\
\hline
\hline
& &\\
Total & 100 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip
\bigskip
\bigskip

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par
\bigskip \bigskip
\noindent Please circle your TA: \hspace{.5in} Andrew 
 \hspace{.5in} David
 \hspace{.5in} Keith
 \hspace{.5in} Victor

\newpage
\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr 
\points{9} 
Let $p$ be a prime.  Prove that if $p\bmod 3 = 1$,
then $p\bmod 6 = 1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr 
\points{9} 
Prove by induction that $3\divides (n^3 + 2n)$ for all $n\in\nats$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr
\points{10} 
\bparts
\ppart	Use Euclid's algorithm to find the gcd of 221 and 323.
\ppart	Find an integer solution to $221x + 323y = 187$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr 
\points{10} 
A \defi{$k$-coloring} of an undirected graph $G=(V,E)$
is a function $\chi:V\to \set{1,2,\ldots,k}$ such that $(u,v)\in E$
implies $\chi(u)\neq \chi(v)$.
\bparts

\ppart Assign the numbers $1$, $2$, $3$, and $4$ to the vertices of the
following graph to demonstrate that the graph has a $4$-coloring.

\ppart Let $G$ be an undirected graph in which the maximum degree of
any vertex is~$d$.  Use induction to prove that $G$ has a
$(d+1)$-coloring.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\remove{
  \pr 
  \points{}
  Let $R_1\subseteq S\times S$ and $R_2\subseteq S\times S$ be two equivalence
  relations on a set~$S$.
  \bparts
  \ppart
  Is their union, the relation $R_1\cup R_2$, an equivalence relation?
  Prove your answer.
  \ppart
  Is their intersection, the relation $R_1\cap R_2$, an equivalence relation?
  Prove your answer.
  \eparts
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr
\points{30}
For each of the following statements, 
(1) circle {\bf T} or {\bf F}  to indicate whether the statement is 
true or false, respectively, and 
(2) justify your answer succinctly.
The justification counts for more points than does the correct 
{\bf T}/{\bf F} answer.
A formal proof is not necessary, but you should be able to write a
one- or two-sentence explanation or picture that conveys the essential
idea.

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
\setlength{\labelwidth}{\leftmargin}%
\setlength{\itemsep}{1.3in}%
\addtolength{\labelwidth}{-\labelsep}
}

\item For all $a,b\in\ints$, every common divisor of $a$ and $b$ 
can be expressed in the form $ax + by$ for some $x,y\in\ints$.

\item For any predicates $P(x)$ and $Q(x)$, we have 
$\forall x \left( P(x)\land \neg Q(x)\right) \implies
\neg\exists x \left( P(x)\implies Q(x)\right)$.

\item
For any prime $p$, we have $(p\divides 1) \implies (p^2+1 \mbox{ is odd})$.

\item
For any two different Fibonacci numbers $F_m$ and $F_n$, 
we have $\gcd(F_m,F_n)=1$.

\item
Every undirected graph in which each vertex has degree 3 has an even
number of vertices.

\item No relation can be both symmetric and antisymmetric.

\item If $R_1\subseteq S\times S$ and $R_2\subseteq S\times S$ are two 
transitive relations on a set~$S$, then their union, the relation 
$R_1\cup R_2$, is also a transitive relation.

\item
$f(x)=x^3-x$ is an injection from $\reals$ to $\reals$.

\item
$f(x)=x^3-x$ is a surjection from $\reals$ to $\reals$.

\item
If $C$ is a countable set, then $C\times C$ is also countable.

\end{list}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr
\points{10}

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $O$, $\Omega$, and $\Theta$ depending depending on
whether $f(n)=O(g(n))$, $f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$.
If there is more than one relation between $f(n)$ and $g(n)$, write
only the strongest one.  {\em Wrong answers will be penalized, so do
not guess unless you are reasonably sure.} The first line is an example
solution.

\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
\renewcommand{\arraystretch}{4}
\begin{array}{rcrl}
2n 		& = & \blank & (n) \\
2^{(\lg^3 n)} 	& = & \blank & (n^3) \\
\lg (n^3) 	& = & \blank & (\lg n)\\
(n - 1)^2/2  	& = & \blank & (n^2) \\
2^{\log_3 n} 	& = & \blank & (n^2)\\
n^{3.01} 	& = & \blank & (n^3\lg n)
\end{array}
\]
\remove{
  \renewcommand{\arraystretch}{3}
  \begin{array}{lrcrl}
  0. \hspace{.5in} & 2n 	& = & \Theta & (n) \\
  1. & 2^{(\lg^3 n)} 	& = & \blank & (n^3) \\
  2. & \lg (n^3) 		& = & \blank & (\lg n)\\
  3. & (n - 1)^2/2  	& = & \blank & (n^2) \\
  4. & 2^{\log_3 n} 	& = & \blank & (n^2)\\
  5. & n^{3.01} 		& = & \blank & (n^3\lg n)
  \end{array}
  \]
}
\renewcommand{\arraystretch}{1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr
\points{10}
Show that in any set of 10 integers, there are 4 integers
$a_1,...,a_4$ such that $3\divides (a_i-a_j)$ for all $i,j\in\set{1,2,3,4}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr
\points{12}
Evaluate the following sums.  Show your work.
Please draw a box around each of your answers.  

\bparts

\ppart Find a closed form expression for
$\displaystyle \sum_{k=0}^\infty \left( 9\over 10\right)^k$.

\ppart Find a closed form expression for
$\displaystyle \sum_{k=0}^\infty k/3^k$.

\ppart Find a tight asymptotic bound for 
$\displaystyle\sum_{k=1}^n 1/\sqrt{k}$.\\
(That is, find an function $f(n)$ in closed form such that 
$f(n) \sim \displaystyle\sum_{k=1}^n1/\sqrt{k}$.)
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\remove{
\pr
\points{??}
The cookie monster is searching the supermarket for cookies.
He does not know which aisle contains the cookies, and he can tell if an 
aisle has cookies if he peers down that aisle from the front of the store.  
Being a large monster (but dumb---he cannot read the signs),
in one step he can move from the front of one aisle to the front of either
adjacent aisle.  He begins at aisle 0 (the center aisle) and follows 
the following search strategy.
He first moves one step to the right to peer down aisle 1, then moves two steps
to the left to peer down aisle~$-1$, then moves five steps to the right to 
aisle~$4$ (inspecting the aisles in between as he moves),
and in general going back and forth between aisle $m^2$ and aisle $-m^2$,
for $m=1,2,3,\ldots$~\
We wonder how efficient this search strategy is.
With today's very large supermarkets in mind, 
we are really interested in asymptotic efficiency.
Find a simple expression $f(n)$ such that if the cookies are in aisle $n$,
the cookie monster takes $\Theta (f(n))$ steps to find them.
% 	that is~$\Theta (s(n))$.
%	---how many steps $s(n)$ the
%	cookie monster takes if the cookies are in aisle~$n$.
}


\remove{
  \pr
  \points{??}
  Let $A$ and $C$ be $n\times n$ matrices where $a_{i,j} = 1$ if city $j$ 
  can be reached within a single day of air travel from city $i$, 
  and $c_{i,j} = 1$ if city $j$ can be reached with a single day of car travel 
  from city $i$.  Otherwise entries are 0.  
  Show how to compute a matrix $M$ where
  $m_{i,j} =1$ iff city $j$ can be reached from city $i$ by a single day of air
  travel followed by a single day of car travel.  Also show how to compute
  $M'$ where $m'_{i,j} =1$ iff city $j$ can be reached from $i$ with 2 days of 
  travel (at most) where each day is all car or all air.  
}

\remove{
\pr
\points{??}
For each function $f(n)$ along the left side of the table below and
each function $g(n)$ across the top, write $O$, $\Omega$, or $\Theta$
in the appropriate space, depending on whether $f(n)=O(g(n))$,
$f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$.  If there is more than
one relation between $f(n)$ and $g(n)$, write only the strongest one.
{\em Wrong answers will be penalized, so do not guess unless you are
reasonably sure.} The first line is a demo solution.

\[
\begin{array}{|c||c|c|c|}
\hline
& \hspace*{1in} & \hspace*{1in} & \hspace*{1in} \\
& n & n\lg n & n^2\\
& & & \\
\hline
\hline
& & & \\
3n\lg n & \Omega & \Theta & O \\
& & & \\
\hline
& & & \\
n^{0.99} \lg^2 n& & & \\
& & & \\
\hline
& & & \\
2n^2-5n\lg n& & & \\
& & & \\
\hline
& & & \\
\lg(n!)& & & \\
& & & \\
\hline
& & & \\
3^{\lg n}& & & \\
& & & \\
\hline
& & & \\
{\displaystyle \sum_{i=1}^n\lg i}& & & \\
& & & \\
\hline
\end{array}
\]
}


\end{problems}

\end{document}


