\documentstyle[12pt,macpsfig,amssymb]{article}
\input{/a/class/6.042/spring95/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}{March 15, 1995}


\begin{closeitemize}
\item This quiz is open book. 

\item Put your name on the top of each page---the pages of this booklet  
will 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 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.  {\bf Be neat}.

\item This quiz ends at 9 {\sc p.m.} It contains six problems.  The 
problems are 16 points each, and you will get 4 points for writing
your name, recitation TA and time clearly. 

\item GOOD LUCK!
\end{closeitemize}

\bigskip
\bigskip

\renewcommand{\arraystretch}{.5}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
name & 4 & \\& &\\ \hline & &\\
1 &  16 & \\& &\\\hline & &\\
2 &  16 & \\& &\\\hline& &\\
3 &  16 & \\& &\\\hline& &\\
4 &  16 & \\& &\\\hline& &\\
5 &  16 & \\& &\\\hline& &\\
6 &  16 & \\& &\\
\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 recitation TA:
 \hspace{.7in} Ravi
 \hspace{.7in} Steve

\bigskip
\bigskip

\noindent Please circle your recitation time: 
\hspace{.5in} 1
\hspace{.5in} 2
\hspace{.5in} 3
\newpage
\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr 
\points{16} 

Discover and prove a formula for $ \left( \begin{array}{cc}
					1 & 1\\
					0 & 1
				\end{array} \right) ^n$.

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

\pr  
\points{16} 

Prove that the following two sequences are equal:

\begin{eqnarray*}
u_0 & = & 2 \\
u_{n+1} & = & u_n^2-u_n+1
\end{eqnarray*} 

\begin{eqnarray*}
v_0 & = & 2 \\
v_{n+1} & = & 1+v_0v_1\cdots v_n
\end{eqnarray*} 

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

\pr 
\points{16} 

For a function $f:A\mapsto B$ and a subset $C\subseteq A$, define
$f(C)=\{b\mid f(a)=b\hbox{  for some }a\in C\}$. Prove that if $f$ is 
a 1-1(an injection), then $f(C\cap D)=f(C)\cap f(D)$ for 
every $C,D\subseteq A$.

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

\pr
\points{16}
 
Define the poset $(\{1,2,3,4,5\}^2,\prec)$ where $(a,b)\prec(c,d)$ 
iff $a\le c$ and $b\le d$.
\bparts
\ppart
Give an antichain which is as long as possible.
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\ppart
Prove that the above antichain is the largest.
\eparts

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

\pr  
\points{16} 
The {\em complement} of an undirected graph $G=(V,E)$ is the graph 
$G^c=(V,E^c)$. 
That is, $G^c$ contains exactly those edges that are not in $G$. 
Prove that if $G$ is not connected then $G^c$ is.

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

\pr
\points{16} 

Give an explicit bijection between $\reals$ and $(0,\infty)$, where 
 $(0,\infty)$ is the set $\{ x \in \reals \mid x > 0 \} $. 

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


\end{problems}

\end{document}


