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

\begin{document}

\exam{Quiz 1}{October 19, 1991}


\begin{closeitemize}

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

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

\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 & 10 & \\
& &\\
\hline
& &\\
2 & 10 & \\
& &\\
\hline
& &\\
3 & 10 & \\
& &\\
\hline
& &\\
4 & 10 & \\
& &\\
\hline
& &\\
5 & 10 & \\
& &\\
\hline
& &\\
6 & 10 & \\
& &\\
\hline
& &\\
7 & 10 & \\
& &\\
\hline
& &\\
8 & 10 & \\
& &\\
\hline
& &\\
9 & 10 & \\
& &\\
\hline
& &\\
10 & 10 & \\
& &\\
\hline
\hline
& &\\
Total & 100 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip
\bigskip
\bigskip

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par

\newpage
\begin{problems}

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

\pr 
\points{??} 
\bparts
\ppart Let $p$ be a prime.  Prove that if $p\bmod 3 = 1$ 
then $p\bmod 6 = 1$.
\ppart Prove that $3\divides (n^3 + 2n)$ for all $n\in\nats$.
\eparts

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


%	DONE BY RANDALL IN RECITATION.
%	\pr
%	\points{??} Use induction to prove that for any natural number $n>3$, 
%	$n! > 2^n$.


\pr
\points{??} Let $G=(V,E)$ be a free tree, and define the relation\\
$R=\{(v_1,v_2)\in V\times V: \mbox{ there is a simple path of even length
from $v_1$ to $v_2$} \}$.
\bparts
\ppart	Prove that $R$ is an equivalence relation.
\ppart	What are the equivalence classes for the graph $G$ below?
\eparts


\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, $R_1\cup R_2$, an equivalence relation?
Prove your answer.
\ppart
Is their intersection, $R_1\cap R_2$, an equivalence relation?
Prove your answer.
\eparts


%	\pr
%	\points{??}
%	Prove that the quotient and the remainder promised by the division
%	algorithm when $a\in\nats$ is divided by $b\in\nats$ are unique.
%
%	\pr
%	\points{??}
%	The media reported that the recent survey 
%	{\em Sex in America$^{\sc pg-13}$} found that in America, men have 
%	kissed(!) an average of six women and women have kissed an average of 
%	two men.  Comment from a graph-theoretic point of view.


\pr
\points{??}
Circle {\bf T} or {\bf F} for each of the following statements to
indicate whether the statement is true or false, respectively.  
Also justify your answer, concisely and succinctly.
The justification counts for more points than simply the correct 
{\bf T}/{\bf F} answer.
One- or two-sentence explanations or pictures should suffice.

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
\setlength{\labelwidth}{\leftmargin}%
\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$.

%\vspace*{1.25in}

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

%\vspace*{1.25in}

\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$, $\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
$f(x)=x^2-x$ is an injection from $\reals$ to $\reals$.

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

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

\item
$n=o(2^{\sqrt{n}})$.

\item
$2^{\lg ^3n} = \Theta ( n^3)$.

\item
$\lg (n^3) = \Theta (\lg n)$.

\item
$n^{3.01} = \omega (n^3 \lg n)$.

\item
$3^{2n} \sim 9^n$.

\item
$e^{\ln (n^3)} = \Theta( n^3 )$.

\item
$1+{1\over 0.9} + \left(1\over 0.9\right)^2 + \left(1\over 0.9\right)^3 \cdots
 = {1\over 1-0.9} = 10$

\end{list}


%	\pr
%	\points{??}
%	Find an $f(n)$ in closed form such that 
%	$f(n)\sim \sum_{i=1}^{n} i^{-1/2}$.


\pr
\points{??}
%	Easy form:  
%	Show that in any set of 10 integers, there are four integers
%	$a_1,...,a_4$ such that for all $i,j$,  $3\divides (a_i-a_j)$.
%	Hard form: 
Show that if $n>m(m-1)$, then
in any set of $n$ integers there are $m$ integers
$a_1,...,a_m$ such that for all $i,j$ we have $m\divides (a_i-a_j)$.


\pr
\points{??}
Let $T_n$ denote the product of all positive even integers less than~$n$.
\bparts
\ppart
Find a closed form expression for $T_n$. 
(You may leave factorials 
%and floor functions 
in your answer.)  
\ppart
Find a function $f(n)$ that does not have sums, products,
floors or factorials for which $f(n) \sim T_n$.
\eparts


\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 step 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---how many steps $s(n)$ the
cookie monster takes if the cookies are in aisle~$n$.
We are interested in asymptotic efficiency, for today's very large 
supermarkets:  
Find a simple expression $f(n)$ that is~$\Theta (s(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}




