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

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

\setcounter{page}{0}

\begin{document}

\qsol{1}{October 16, 1996}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\problem
Prove or disprove\\
\begin{displaymath} 
\forall n \in \naturals,  \sum_{i=0}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6}
\end{displaymath}

\bigskip


{\em Base case.} $P(0)$ is true since \\

${\displaystyle \sum_{i=0}^{0} i^2 = 0 =  \frac{0(0+1)((2)(0)+1)}{6}}$. \\

{\em Inductive step.} Assume $P(n)$ is true. Then
\[ {\displaystyle \sum_{i=0}^{n} i^{2}  =  \frac{n(n+1)(2n+1)}{6}}.\] \\

$
\begin{array}{lccr}
{\displaystyle \sum_{i=0}^{n+1} i^{2}} & = & 
{\displaystyle \sum_{i=0}^{n} i^{2}} + (n+1)^2 & \\
& = & \frac{n(n+1)(2n+1)}{6} + (n+1)^2 &  \\
& = & (n+1) \frac{2n^2+7n+6}{6} & \\
& = & \frac{(n+1)(n+2)(2n+3)}{6} \\
\end{array}$

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

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%4
%2
\problem
An infinite sequence of natural numbers $a_1, a_2, a_3$, \ldots is
defined in such a way that $a_1 = 14, a_2 = 35$, and each later
$a_i$, $i \geq 3$, is obtained using one of the following rules:\\

\vspace{.01in}
{\bf Rule A} Choose any two preceding elements of the sequence and define $a_i$
to be their sum. \\

\vspace{.01in}
{\bf Rule B} Choose any number $k \geq 1$ of preceding elements of the sequence,
and define $a_i$ to be their product divided by $7^{k-1}$. \\

\vspace{.01in}
Use the well-ordering principle to prove that every element in the
sequence is a  multiple of $7$. 
({\it Hint:  In case you have forgotten, the well-ordering principle says
that every nonempty set of naturals has a smallest element.})

\bigskip
\begin{proof}
Let $S =$ \{all elements in the sequence that are not multiples of $7$ \}. \\
Assume that $S$ is nonempty.  Then, by well-ordering, it has a smallest 
element $a_{n}$. \\
If  $a_{n}$ is obtained by rule A,  then $a_{n} = a_{i} +  a_{j}$ 
for some  $a_{i}$ and $a_{j}$ smaller than $a_{n}$. But then  $a_{i}$ and
$a_{j}$ are multiples of $7$ therefore $a_{n}$ has to be a multiple of $7$
also. \\
If  $a_{n}$ is obtained by rule B, then there are $k$ smaller elements
in the sequence ,that are multiples of $7$, so we can write them in the form
$a_{k} = 7n_{k}$. $a_{n}$ is the product of the $a_k$
divided by $7^{k-1}$.  Then we can write \\

\begin{displaymath}
a_{n} = (\prod_{i=1}^{k} (7n_{i}))/7^{k-1} = 7(\prod_{i=1}^{k} n_{i})
\end{displaymath}

Therefore $a_{n}$ is also a multiple of $7$.
\end{proof}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\problem
Using Euclid's algorithm, or otherwise, find an $x$ such that \\
$$43x \equiv 1 \pmod {105}. $$

\bigskip


$
\begin{array}{lccrr}
        & 105   & 43   & -9    & 22 \\
2       & 43   & 19    & 4   & -9  \\
2       & 19   & 5     & -1    & 4 \\
3       & 5    & 4     &1    & -1  \\
1       & 4    & 1     & 0     &1  \\
1       & 1    & 0     & 1     & 0  \\

\end{array}$

So  $x = 22$.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%4
\problem
Let $f:U \rightarrow V$ be an arbitrary function and $A,B$ be arbitrary 
subsets of $U$. Prove or disprove the following claims.\\
a) $f(A \cap B) = f(A) \cap f(B)$ \\

\bigskip
Not True. Let $A = \{ 1 \} , B = \{ -1 \} , f(x) = x^2$. \\

\bigskip
   
b) $f(A \cup B) = f(A) \cup f(B)$

\bigskip
True. \\
\begin{proof} First we show $f(A \cup B) \subseteq f(A) \cup f(B)$. \\

\begin{math}
x \in f(A \cup B) \Rightarrow (f^{-1}(x) \subseteq A) \vee
( f^{-1}(x) \subseteq B) \\
\Rightarrow (x \in f(A)) \vee (x \in f(B)) \\
\Rightarrow x \in f(A) \cup f(B). \\
\end{math}

Now we show that $f(A) \cup f(B) \subseteq f(A \cup B)$. \\

\begin{math}
x \in f(A) \cup f(B) \Rightarrow (x \in f(A)) \vee (x \in f(B)) \\
\Rightarrow (f^{-1}(x) \subseteq A) \vee (f^{-1}(x) \subseteq B) \\
\Rightarrow f^{-1}(x) \subseteq A \cup B \\
\Rightarrow x \subseteq f(A \cup B). \\
\end{math}

\end{proof}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%6
%5
\problem
Which of the following functions are bijections?  If a function is a bijection 
write down its inverse.

\bparts

\ppart $f: \reals \rightarrow \reals , f(x) = x$ \\

{\bf Injection} $x \neq y \Rightarrow f(x) \neq f(y)$ \\
{\bf Surjection} $ \forall r \in \reals , \exists x ,
(x  = r) , s.t.  f(x) = r$. \\
{\bf Inverse} $f^{-1}(x) = x$. \\


\ppart $f: \reals^{+} \rightarrow \reals^{+} , f(x) = \frac{1}{x}$ \\

{\bf Injection} $x \neq y \Rightarrow \frac{1}{x} \neq \frac{1}{y}$ \\
{\bf Surjection} $ \forall r \in \reals , \exists x , 
(x  = \frac{1}{r}) ,  s.t.  f(x) = r$. \\
{\bf Inverse} $f^{-1}(x) = \frac{1}{x}$. \\

\ppart $f: \naturals \rightarrow \naturals , f(x) = x^{2}$ \\
This function is not a bijection because it is not a surjection.  
For example, there is no $n \in \naturals$ such that $n^2 = 3$. \\

\ppart $f: \reals \rightarrow \reals , f(x) = x^{3}$

{\bf Injection} $x \neq y \Rightarrow x^3 \neq y^3$ \\
{\bf Surjection} $ \forall r \in \reals , \exists x , 
(x  = r^\frac{1}{3})  , s.t.  f(x) = r$. \\
{\bf Inverse} $f^{-1}(x) = x^\frac{1}{3}$. \\


\eparts

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%6
\problem

Prove that among any set of 150 natural numbers, there must be three
numbers, $a$, $b$, and $c$, such that all the pairwise differences,
$a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70.

\bigskip

\begin{proof}
Use Pigeonhole. \\
{\bf Pigeons} The 150 numbers. \\
{\bf Holes} The natural numbers mod $70$. \\
There is some hole with $ \ceil{\frac{150}{70}} = 3$ pigeons, that is, 
three numbers $a,b,c$ that are equivalent modulo $70$. Then their differences
are equivalent to $0$ modulo $70$, therefore they are divisible by $70$.
\end{proof}
\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%7
\problem

For each of the following sets, either use diagonalization to prove
that the set is uncountable, or else use dovetailing or another
technique to show that the set is countable. \\
(If an answer to one part of the question follows from an answer you
have already given to another part, then you need only indicate this
-- you don't need to give a direct proof of the part that follows.) \\

\bparts
\ppart The set $E$ of all the even natural numbers. \\

\bigskip
This set is countable.  The function $f(n) = 2n$ is a bijection from $\naturals$
to $E$.

\bigskip
\ppart The set of all subsets of $E$. \\

\bigskip
This set is uncountable.  The power set of any set has bigger cardinality than
the original set.  \\

\bigskip
\ppart The set of all finite subsets of $E$. \\

\bigskip
\ Let $S_{i} =$ { The set of all subsets of E with $i$ elements. } \\
Each of the $S_{i}$ is countable and the set under question  is the countable 
union of all the $S_{i}$, therefore it is countable. \\

\bigskip
\ppart The set of all even-size finite subsets of $E$. \\

\bigskip
This set is countable, being a subset of the set in part (c). \\

\eparts

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%8
\problem

The CS department has just completed a revamping of its curriculum.  
The following 10 courses are now required:
6.001, 6.002, 6.003, \dots , 6.009, and 6.042.\\
In addition, for every $i,j$, 6.00$i$ is a prerequisite of 6.00$j$ or 6.0j,
if $i < j$ and $gcd(i,j) > 1$.   \\

\vspace{.01in}

\bparts
\ppart Write down all the elements of the {\em prerequisite} relation. \\

\bigskip
{\em prerequisite} $=$
\{ (6.002,6.004) , (6.002,6.006) , (6.002,6.008) , (6.002,6.0042) \\
   (6.003,6.006) , (6.003,6.009) , (6.003,6.042) , (6.004,6.006) \\
   (6.004,6.008) , (6.004,6.042) , (6.006,6.008) , (6.006,6.042) \\
   (6.007,6.042) , (6.008,6.042) , (6.009,6.042) , (6.006,6.009) \} \\

\bigskip 
\ppart State whether this relation is reflexive, symmetric, transitive,
antisymmetric. Is it an equivalence relation? \\

\bigskip
The relation is antisymmetric, but nothing else. \\

\vspace{3.5in}


\begin{center}
Problem continued on the next page.
\end{center}

\newpage
\ppart Now consider the {\em taken before} relation which is defined to be the
reflexive and transitive closure of the {\em prerequisite} relation.
Draw the Hasse Diagram for the {\em taken before} relation. \\

\vspace{2.5in}   
\ppart The new regulations place no limit on how many courses a student can 
take in one term.
What is the minimum number of terms required to complete all the required 
courses? Why? \\

\bigskip
The minimum number of terms is $5$, which is the length of the critical path
in the above Hasse diagram. \\

\bigskip
\ppart Write down a maximum-size antichain in the partial order. 
What is the meaning of an antichain in terms of a student's schedule?\\  

\bigskip
6.001, 6.002, 6.003, 6.005, 6.007. \\
An antichain is a list of subjects that a student can take at the same term. \\

\eparts


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%9
\problem
A {\em Tournament Graph} is a directed graph such that if $u$ and $v$ are 
vertices then either $(u,v)$ is an edge or $(v,u)$ is an edge but not both. 
A {\em Directed Hamiltonian Path} is a simple path in a directed graph that 
contains every vertex exactly once. \\
Prove that every tournament graph has a directed Hamiltonian path. 
({\it Hint: Use induction on the number of vertices.} )

\bigskip

\begin{proof}
We use induction on the number of vertices $v$ in the graph.
So let $P(v)$ be the predicate ``Every tournament graph with v vertices
has a hamiltonian path''.

{\bf Base case} 
$P(2)$. Let $V = \{x_1, x_2 \}$. 
There are two possible tournament
graphs, one in which $(x_1, x_2)$ is the only  edge, and one in
which $(x_2, x_1)$ is the only edge. In both cases, the existence of a
hamiltonian path is clear (just follow the edge). \\

{\bf Inductive step}
Now suppose $P(v)$ is true. We want to establish $P(v+1)$.
So let $T=(V,E)$
be a tournament graph with $v+1$ vertices. Pick some vertex $x$ in $V$.
 Let
$T'$ be the subgraph of $T$ with vertex set $V' = V- \{x \}$ and edge set 
$ E' $
consisting of all edges in $ E$ that connect vertices in $V'$. It is easily
verified that this graph is a tournament with $v$ vertices, and hence,
since we assume $P(v)$ to be true, it contains a hamiltonian path 
$x_1,x_2, .., x_v$. There are three cases to consider. \\

\begin{enumerate}

\item Suppose first that $(x, x_1)$ is in $E$. In this case, 
$x,x_1, .., x_v$ is a hamiltonian path in $T$. 

\item Suppose that $(x, x_1)$ is not in $E$, but $(x_v, x)$ is. In this case,
$x_1, ..., x_v, x$ is a hamiltonian path in $T$.

\item Suppose that neither $(x, x_1)$ nor $(x_v, x)$ is in $E$.
 This means that
$(x_1, x)$ and $(x, x_v)$ are in $E$. Let $S$ be the set of 
$i \in \{1, ..., v \}$      
such that $(x, x_i)$ is in $E$. By assumption, $v$ is in $S$.
 Hence $S$ is nonempty. 
By the well-ordering principle, there is a smallest element
$l$ of $S$. By assumption, $l > 1$. It follows that $(x_{l-1}, x)$ and 
$(x, x_l)$
are both in $E$. We can then construct the hamiltonian path 
$x_1, \ldots ,x_{l-1}, x, x_l, .., x_v$ in $T$.

\end{enumerate}

We conclude that $P(v+1)$ is true, and hence $P(v)$ is true for all natural
numbers by induction.
\end{proof}


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%10
\problem
Consider a state machine whose states consist of values for the
following variables, all in $\naturals$: \\

\vspace{.05in}
$x$, $y$: initially arbitrary positive naturals \\
$a$: initially $1$ \\
$r$, $s$: initially equal to $x$ and $y$, respectively \\

\vspace{.05in}
Its transitions are those of the following two kinds: \\

\begin{enumerate}

\item $\it{even}$ \\
Precondition: 

\hspace{.1in} $s$ is even \\

\hspace{.1in} $s > 0$ \\
Effect: 

\hspace{.1in} $r := r^2$ \\

\hspace{.1in} $s := {s \over 2}$ \\

\item $\it{odd}$ \\
Precondition: 

\hspace{.1in} $s$ is odd \\
Effect:

\hspace{.1in} $a := a \times r$ \\

\hspace{.1in} $r := r^2$ \\

\hspace{.1in} $s := {s-1 \over 2}$ \\

\end{enumerate}

\bigskip
Use induction on the length of an execution to prove the following
invariant of this state machine: \\

\begin{center}
If $s = 0$ then $a = x^y$.
\end{center}

({\it Hint:  You will need to strengthen this invariant in order to prove it
by induction.} )


\newpage

\bigskip
We are going to show the invariant $x^y = (r^s)a$ \\

{\em Base case:} 
Initially
$r = x, s = y, a = 1$,  therefore
$x^y = (r^s)a$. \\

{\em Induction Step} \\

\begin{itemize}
\item s is even \\
$q^{'}.r = (q.r)^2$ \\
$q^{'}.s = (q.s)/2$ \\
$((q.r)^2)^{\frac{q.s}{2}}(q.a) = (q.r)^{q.s}(q.a) = x^y $\\

\item s is odd \\
$q^{'}.r = (q.r)^2$ \\
$q^{'}.s = (q.s-1)/2$ \\
$q^{'}.a := (q.a)(q.r)$ \\
$((q.r)^2)^{\frac{q.s-1}{2}}(q.a)(q.r) = (q.r)^{q.s}(q.a) = x^y$\\

\end{itemize}

The induction is complete.
If we set $s = 0$ in our invariant, we obtain $a = x^y$. \\


\end{problems}

\end{document}




















