\documentstyle[12pt,macpsfig,amssymb]{article}
\input{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}

\pquiz{1}{October 05, 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 practice quiz contains nine problems.  (THE REAL QUIZ 
WILL CONTAIN FEWER PROBLEMS) The problems are 11 points each, and you
will get 1 point for writing your name 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 & 1 & \\& &\\ \hline & &\\
1 &  11 & \\& &\\\hline & &\\
2 &  11 & \\& &\\\hline& &\\
3 &  11 & \\& &\\\hline& &\\
4 &  11 & \\& &\\\hline& &\\
5 &  11 & \\& &\\\hline& &\\
6 &  11 & \\& &\\\hline& &\\
7 &  11 & \\& &\\\hline& &\\
8 &  11 & \\& &\\\hline& &\\
9 &  11 & \\& &\\
\hline
\hline
& &\\
Total & 100 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip
\bigskip
\bigskip

\newpage
\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\problem 
\points{11} 
Prove by induction that $3 | (n^3 + 2n)$ for all $n \in \naturals$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\problem 
\points{11} 
Prove that all rectangles with integer dimensions, except for the $1
\times 1$ rectangle, can be tiled with tiles of dimension $1\times 2$
and $1\times 3$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\problem 
\points{11} 
\bparts
\ppart Use Euclid's algorithm to find the $gcd$ of $221$ and $323$.
\vspace*{-2in}
\ppart Find an integer solution to $221x + 323y = 187.$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%4
\problem 
\points{11} 
Show that in any set of $10$ integers, there are $4$ integers $a_1, a_2, a_3$ and $a_4$ such that $3 | (a_i - a_j)$ for all $i,j \in \{1,2,3,4\}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%5
\problem 
\points{11} 
Let $f: A \rightarrow B$ and $g: B \rightarrow C$ be functions. Answer the questions below and justify your answers.
\bparts
\ppart If $g\circ f: A \rightarrow C$ is a surjection, are $f$ and $g$ necessarily surjections?
\vspace*{-2in}
\ppart If $g\circ f: A \rightarrow C$ is an injection, are $f$ and $g$ necessarily injections?
\vspace*{-2in}
\ppart If $g\circ f: A \rightarrow C$ is a bijection, are $f$ and $g$ necessarily bijections?
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem 
\points{11}
Some real numbers have multiple decimal representations (e.g.,
$0.2999\ldots = 0.3000\ldots$). Let $S$ be the set of all such real
numbers. Is $S$ countable or uncountable? Justify your answer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%7
\problem
\points{11}
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 a chain which is as long as possible.
\vspace*{-2in}
\ppart Prove that the above chain is the largest.
\vspace*{-2in}
\ppart If the above were a poset of tasks with dependencies how many 
time steps would it take to execute all the tasks given an arbitrary
number of processors? (Assume each task takes one time step on any
processor.)
\vspace*{-2in}
\ppart Identify all the minimum elements.
\vspace*{-2in}
\ppart Specify the elements of a largest antichain.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%8
\problem  
\points{11} 
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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%9
\problem 
\points{11} 
Discover and prove (by induction) a formula for $ \left( \begin{array}{cc}
					1 & 1\\
					0 & 1
				\end{array} \right) ^n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}

\end{document}







