\documentstyle[12pt,macpsfig,psfig,amssymb]{article}
\input{macros-course}

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

\setcounter{page}{0}

%\newcommand{\pr}{\problem}

\begin{document}

\pquiz{1}{October 3, 1996}

\center{(Quiz \#1 and Solutions, Fall 1995)}

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\problem
\bparts
\ppart Use Euclid's algorithm to find the $gcd$ of $241$ and $178$.
\bigskip

$
\begin{array}{lccrr}
        & 241   & 178   & 65    & -88 \\
1       & 178   & 63    & -25   & 65  \\
2       & 63    & 52    & 19    & -23 \\
1       & 52    & 11    & -4    & 19  \\
4       & 11    & 8     & 3     & -4  \\
1       & 8     & 3     & -1    & 3   \\
2       & 3     & 2     & 1     & -1  \\
1       & 2     & 1     & 0     & 1   \\
2       & 1     & 0     & 1     & 0  
\end{array}$

Hence, $gcd(241,178) = 1$.

\ppart Find an integer solution to $241x + 178y = 10.$

\bigskip
From part a) we have 
\[ gcd(241,178) = 65\cdot 241 - 88\cdot 178 = 1.\]
Multiplying by $10$ we get
\[ 650\cdot 241 - 880\cdot 178 = 10.\]
Hence, one solution is $x = 650$ and $y = -880.$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\problem 
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 Prove that there exist two distinct non-empty 
sets $A$ and $B$ such that $\Sigma(A) = \Sigma(B)$.

\bigskip
\begin{proof}
Consider ${\cal C} = {\cal P}(S) - \{S,\phi\}$. This is the collection
of all nonempty subsets of $S$, excluding $S$. $|{\cal C}| = 2^n -2$.
For any $A \in {\cal C}$ it is the case that $1 \leq \Sigma(A) \leq
2^n - 3$. It is clear that $1 \leq \Sigma(A)$ since $S$ is a set of
positive integers and $A$ is a nonempty subset of it. It is also clear
that $\Sigma(A) \leq 2^n - 3$, since $A$ is a proper subset of $S$ and
hence $\Sigma(A) < \Sigma(A) \leq 2^n - 2$.

Thus we have $2^n-2$ elements $A$ in ${\cal C}$ such that $1 \leq
\Sigma(A) \leq 2^n - 3$. By the pigeonhole principle, we have that there exist two sets $A, B \in {\cal C}$ such that  $\Sigma(A) = \Sigma(B)$. By construction we have that $A$ and $B$ are distinct non-empty subsets of $S$.
\end{proof}
\ppart Prove that there exist two distinct non-empty 
sets $A$ and $B$ such that $\Sigma(A) = \Sigma(B)$ and $A \cap B =
\phi.$

\bigskip
\begin{proof}
Let $A'$ and $B'$ be the two sets from part a). It is the case that
$A' \not\subset B'$ and $B' \not\subset A'$ because for any two sets
$P,Q \subset S$ it is the case that $P \subset Q \Rightarrow \Sigma(P)
< \Sigma(Q)$.

Now consider, $A = A' - A' \cap B'$ and $B = B' - A' \cap B'$. It is
clear that $\Sigma(A) = \Sigma(B)$ and $A \cap B =
\phi.$ Hence we are done.
\end{proof}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\problem 
\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
\begin{itemize}
\item {\em Reflexivity} $(a,b) \sim (a,b)$ since $a + b = b + a$.
\item {\em Symmetry} $(a,b) \sim (c,d) \Rightarrow (c,d) \sim (a,b)$ since $a + d = b + c \Rightarrow c + b = d + a$.
\item {\em Transitivity} Assume $(a,b) \sim (c,d)$, i.e. $ a + d = b + c$. And, $(c,d) \sim (e,f)$, i.e. $c + f = d + e$. Adding we get $a + d + c + f = b + c + d + e$ or $a + f = b + e$, i.e. $(a,b) \sim (e,f)$. Hence $(a,b) \sim (c,d) \wedge (c,d) \sim (e,f) \Rightarrow (a,b) \sim (e,f)$.
\end{itemize}
Since $\sim$ is reflexive, symmetric and transitive it is an equivalence relation.
\ppart Partition the set $\{0,1,2\} \times \{0,1,2\}$ into the  distinct equivalence classes under $\sim$.
\bigskip
We can rewrite $(a,b) \sim (c,d)$ if $a+d = b+c$ as $(a,b) \sim (c,d)$ if $a-b = c -d$. This shows that with any equivalence class ${\cal C}$ we can associate a {\em difference} $d$ such that $(a,b) \in {\cal C} \Rightarrow a - b = d$. This gives us an easy way to list the equivalence classes of $\{0,1,2\} \times \{0,1,2\}$.
\begin{itemize}
\item $d = -2$ :  $\{(0,2)\}$.
\item $d= -1$ : $\{(0,1),(1,2)\}$.
\item $d= 0$ : $\{(0,0),(1,1),(2,2)\}$.
\item $d= 1$ : $\{(1,0),(2,1)\}$.
\item $d= 2$ : $\{(2,0)\}$.
\end{itemize}
\ppart 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.

\bigskip
$2n+1$ since the difference can be any value in $\{-n,\ldots, n\}$.
\eparts

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

\bigskip
Let $P(n)$ be ``${\displaystyle \sum_{i=1}^n i^3 =  \left(\sum_{i=1}^n i\right)^2}.$''\\
{\em Base case.} $P(1)$ is true since ${\displaystyle \sum_{i=1}^1 i^3 = 1 =  \left(\sum_{i=1}^1 i\right)^2}$. \\
{\em Inductive step.} Assume $P(n)$ is true. Then
\[ {\displaystyle \sum_{i=1}^n i^3 =  \left(\sum_{i=1}^n i\right)^2}.\]

Adding $(n+1)^3$ to both sides we get,

$
\begin{array}{lccr}
{\displaystyle \sum_{i=1}^{n+1} i^3} & = &\left({\displaystyle \sum_{i=1}^n i}\right)^2 + (n+1)^3 & \\
 & = & (n(n+1)/2)^2 + (n+1)^3 & \mbox{since ${\displaystyle \sum_{i=1}^n i} = n(n+1)/2$} \\
 & = &(n+1)^2/4 \times (n^2 + 4(n+1))  & \\
 & = &((n+1)(n+2)/2)^2 & \\
 & = & \left({\displaystyle \sum_{i=1}^{n+1} i}\right)^2
\end{array}$

Hence, $P(n+1)$ is true. Thus $P(n)$ is true for all $n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%5
\problem
$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 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
Reflexivity fails since $(A,A)$ does not belong to the relation of the
tournament.

Transitivity can fail since it could be in a tournament that $A$ beats
$B$ who beats $C$ who in turn beats $A$, i.e. $(A,B)$ and $(B,C)$
could be in the relation of the tournament without there also being
$(A,C)$.

(Note that anti-symmetry holds vacuously, since we never have both
$(A,B)$ and $(B,A)$ in the relation.)

\ppart 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.
\]
\bigskip
\begin{proof}
Let $P(n)$ be ``in any tournament with $n$ teams there exists a
two-step champion.'' \\ {\em Base case.} $P(2)$ is true since in a
tournament with only two teams the winner is a two-step champion. \\
{\em Inductive step.} Assume $P(n)$ is true. Consider a tournament
with $n+1$ teams numbered $1, 2, \ldots, n+1$. Then the games between
teams $1, 2, \ldots, n$ forms a subtournament and hence, by the
inductive hypothesis, it must be the case that this subtournament
possesses a two-step champion. Let this two-step champion be the team
numbered $1$ without loss of generality. Now, if $n+1$ loses to $1$ or
any of the teams that lost to $1$ then it is clear that $1$ is a
two-step champion for the whole tournament. Otherwise, it is the case
that $n+1$ beat $1$ and all the teams that lost to $1$ which makes
$n+1$ the two-step champion. In either case the tournament possesses a two-step champion. Thus $P(n+1)$ is true. Hence $P(n)$ is true for all $n$.
\end{proof}
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem 
\bparts
\ppart 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
\begin{proof}
Suppose the set ${\cal C}$ of real numbers $\in (0,1)$ that have only
$3$s and $7$s in their decimal representation is countable. Then there
exists a bijection $f: \naturals \rightarrow {\cal C}$. Represent this
by a matrix $M$ where $M_{ij} = 3$ if the $j$th digit of $f(i)$ (after
the decimal point) is $3$, and $M_{ij} = 7$ otherwise. Now create a
new number $T$ by considering the diagonal elements $M_{ii}$ of the
matrix. $i$th digit of $T = 3$ if $M_{ii} = 7$, otherwise $i$th digit
of $T = 7$. This is a valid element of ${\cal C}$ and $f^{-1}(T)$ must
exist. But observe that if the $f^{-1}(T)$th digit of $f^{-1}(T)$ is
$3$ then the $f^{-1}(T)$th digit of $f^{-1}(T)$ must be $7$ and
vice-versa. Thus, either way, we have a contradiction. Hence ${\cal
C}$ cannot be countable.
\end{proof}
\ppart Prove that the cross product of two countable sets is countable.
\bigskip
\begin{proof}
Let the two sets be $A = \{a_1,a_2,\ldots\}$ and $B = \{b_1,
b_2,\ldots\}$. We can list the elements of the sets in this fashion
because they are countable and hence have a bijection with the
naturals. We list the cross product, using the idea of dove-tailing shown in class, to get the listing $\{ (a_1,b_1),(a_1,b_2),(a_2,b_1),(a_1,b_3),(a_2,b_2), (a_3,b_1), \ldots \}$. It is easy to see that $(a_i,b_j)$ will occur before position $(i+j)^2$ in our listing. Since we have been able to give a valid listing $A \times B$ is countable.
\end{proof}
\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}







