\documentstyle[12pt,macpsfig,psfig,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}

\examinitials{Quiz 1}{October 11, 1995}


\begin{closeitemize}
\item This quiz is closed book, except for a 2-sided handwritten crib sheet. No calculators allowed.

\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 contains six problems.The problems are 20 points each, 
and you will get 2 points 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 & 2 & \\& &\\ \hline & &\\
1 &  20 & \\& &\\\hline & &\\
2 &  20 & \\& &\\\hline& &\\
3 &  20 & \\& &\\\hline& &\\
4 &  20 & \\& &\\\hline& &\\
5 &  20 & \\& &\\\hline& &\\
6 &  20 & \\& &\\
\hline
\hline
& &\\
Total & 122 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip
\bigskip
\bigskip

\newpage
\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\pr 
\points{20} 
\bparts
\ppart \points{10} Use Euclid's algorithm to find the $gcd$ of $241$ and $178$.
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\vspace*{0.9in}
\ppart \points{10} Find an integer solution to $241x + 178y = 10.$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\pr 
\points{20} 
Let $S$ be a set of $n$ positive integers. For any subset $A \subset
S$ let $\Sigma(A)$ denote the sum of the elements in $A$. You are given that 
$\Sigma(S) \leq 2^n - 2.$ 
\bparts
\ppart \points{15} Prove that there exist two distinct non-empty 
sets $A$ and $B$ such that $\Sigma(A) = \Sigma(B)$.
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\vspace*{0.9in}
\ppart \points{5} Prove that there exist two distinct non-empty 
sets $A$ and $B$ such that $\Sigma(A) = \Sigma(B)$ and $A \cap B = \phi.$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\pr 
\points{20}
Let $(a,b) \sim (c,d)$ if $a+d = b+c$. 
\bparts
\ppart \points{10} Prove that $\sim$ is an equivalence relation on $\integers \times \integers$.
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\ppart \points{5} Partition the set $\{0,1,2\} \times \{0,1,2\}$ into the  distinct equivalence classes under $\sim$.
\bigskip
\bigskip
\bigskip
\bigskip
\ppart \points{5} How many distinct equivalence classes under $\sim$ are there on the set $\{0,1,\ldots, n\} \times \{0,1,\ldots, n\}$. You do not need to prove your answer.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%4
\pr 
\points{20} 
Prove by induction that 
\[ {\displaystyle \sum_{i=1}^n i^3 =  \left(\displaystyle \sum_{i=1}^n i\right)^2}.\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%5
\pr 
\points{20} 
$n$ teams play a tournament. Every team plays every other team exactly
once and all games end in a win/loss. It is possible that weaker teams can beat stronger teams. 
\bparts
\ppart \points{5} Any tournament can be viewed as a relation on the set of teams, 
with $(A,B)$ in the relation iff $A$ beats $B$. Is this relation a
partial order for all tournaments? If yes, prove it. If not list all partial order properties that can fail.
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\ppart \points{15} Show (by induction) that in any tournament
there exists a two-step champion, i.e. there exists a team $A$ such
that for every other team $B$ \\
\[ \mbox{it is the case that   } \left\{ \begin{array}{l}
			\mbox{ $A$ has beaten $B$, or} \\
 			\mbox{ there exists $C$ such that $A$ has beaten $C$ who has beaten $B$.}
			\end{array} \right.
\]
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\pr 
\points{20}
\bparts
\ppart \points{10} Show that the set of real numbers $\in (0,1)$ that have only $3$s 
and $7$s in their decimal representation is uncountable.
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\vspace*{0.5in}
\ppart \points{10} Prove that the cross product of two countable sets is countable.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse
%7
\pr
\points{20}
The following poset shows the ``prerequisite'' dependencies among the computer science courses required for an M.Eng degree at MIT. (It is not factually accurate.) The dependencies go upwards.
\begin{figure}[htbp]
\centerline{\psfig{figure=course6.ps,height=2in}}
\caption{A poset of course 6 prerequisite dependencies}
\label{fig:inter}
\end{figure}
\bparts
\ppart Given that there is no limit to the number of courses an MIT student can take in a term, what is the minimum number of terms needed for an MIT student to to get a course 6 M.Eng degree.
\ppart Harvard students are allowed to enroll for at most two courses a term at MIT. What is the minimum number of terms a Harvard student will take to get a course 6 M.Eng degree. 
\eparts
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}

\end{document}







