%\input{params}
\documentclass[11pt,twoside]{article}
    
\usepackage{graphics}
\newcommand{\nand}{|}

\input{../handouts/macros-course}

\def\cent{{\not\!\mathrm{c}}}

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

\printlayout
\askaboutsolutions

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut3}
\newcommand{\tutnum}{3}
\newcommand{\tutdate}{September 23, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{miniquiz2}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item
%Do they know sets? we asked them to read

\textbf{Velleman 2.3, Ex. 5:} Let $I=\{2,3\}$, and for each $i\in I$
let $A_i=\{i,2i\}$ and $B_i=\{i,i+1\}$.

\begin{enumerate}
\item
List the elements of the sets $A_i$ and $B_i$ for all $i\in I$.\\

\solution{
\medskip
\textbf{Solution:}\\
For $i=2$, $A_i$ = \{2,4\} and $B_i$ = \{2,3\}.\\
For $i=3$, $A_i$ = \{3,6\} and $B_i$ = \{3,4\}.\\
}
\bigskip
\bigskip
\bigskip

\item
Find $\cap_{i \in I}(A_i \cup B_i)$ and $(\cap_{i\in I}A_i)\cup(\cap_{i\in I}B_i)$. Are they the same?

\solution{
\medskip
\textbf{Solution:}
\begin{eqnarray*}
\cap_{i \in I}(A_i \cup B_i)  & = &(A_2 \cup B_2) \cap (A_3 \cup B_3)\\
& = &\{2, 3, 4\} \cap \{3, 4, 6\}\\
& = &\{3, 4\}\\
\end{eqnarray*}

\begin{eqnarray*}
(\cap_{i\in I}A_i)\cup(\cap_{i\in I}B_i) & = & (A_2 \cap A_3) \cup (B_2 \cap B_3)\\
& = &\emptyset \cup \{3\}\\
& = & \{3\}\\
\end{eqnarray*}

Therefore, the two sets are not equal.
}
\end{enumerate}

\vspace{2in}

\end{enumerate}


\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

%\newpage

\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

%\begin{problems}

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem \textbf{ Well ordering}

\textbf{Rosen 3.2, Ex. 58:} 
The well-ordering property can be used to show that there is a unique
greatest common divisor of two positive integers. Let $a$ and $b$
be positive integers, and let $S$ be the set of positive integers of the
form $as+bt$, where $s$ and $t$ are integers.\\
a) Show that $S$ is nonempty.\\
b) Use the well-ordering property to show that $S$ has a smallest 
element $c$.\\
c) Show that if $d$ is a common divisor of $a$ and $b$, then $d$ is
a divisor of $c$.\\
d) Show that $c|a$ and $c|b$. (Hint: First, assume that $c \not| \ a$.
Then $a=qc+r$, where $0<r<c$. Show that $r\in S$, contradicting the
choice of $c$.)\\
e) Conclude from (c) and (d) that the greatest common divisor of
$a$ and $b$ exists. Finish the proof by showing that this 
greatest common divisor of two positive integers is unique.

\renewcommand{\labelenumi}{\alph{enumi}}
\solution{
\medskip
\textbf{Solutions:}\\

\begin{enumerate}
\item
For example, just set $s=1$, and $t=1$.  Then $as+bt = a+b$, which
is a positive integer by our definitions of $a$ and $b$.

\item
The Well Ordering Property states that every non-empty set of non-negative integers has a smallest member.  Since we just showed in part a that the set $S$ is non-empty, it must have a smallest member, which we may call $c$.

\item
If $d$ divides $a$ and $b$, then $d$ divides $as$ and $bt$ for any positive integers $a$ and $b$.  Therefore, $d$ also divides the sum $as+bt$.  Since $c \in S$, c must be such a sum, by our definition of membership in $S$.  Therefore, $d$ can divide $c$.

\item
We will just show $c \nand a$, as the argument is identical to show $c \nand b$.\\  
Proof by Contradiction.\\
Assume for the purpose of contradiction that $c \not \nand \  a$.\\
If $c$ does not evenly divide into $a$, then we can write the expression $a = qc + r$, for some postive integer $r$, where $0<r<c$.\\
We can rewrite this in terms of $r$: $r=a-qc$.\\
Now, since $c \in S$, we know that $c$ is of the form $c=as+bt$, for some integral values of $s$ and $t$.  Rewriting our expression for $r$ again, we get:\\
$r=a-qc = a-q(as+bt)=a-aqs-qbt=a(1-qs)+b(-qt).$  
But now we are done, because we have expressed the positive integer $r$ as a linear combination with integer coefficients of $a$ and $b$.  This means that $r \in S$, which we know is not possible since $r<c$.  Thus, we have a contradiction, and our assumption that $c \not \nand \ a$ must be wrong, so we can conclude that $c \nand a$.

\item
Finally, by part (d), $c$ is a divisor of both $a$ and $b$.  Furthermore, from part (c) we know that any divisor of both $a$ and $b$ is also a divisor of $c$.  This means that every common divisor of $a$ and $b$ is no greater than $c$, and so $c$ is the greatest common divisor of $a$ and $b$.  To see that the greatest common divisor of a number is unique, one just needs to note that it makes no sense to have two numbers, each of which is greater than the other.
\end{enumerate}
}

\renewcommand{\labelenumi}{\arabic{enumi}.}

%\problem \textbf{ Structural Induction}
%
%Definition: the set of rooted trees $T$\\
%1. A single node is in $T$\\
%2. if $t_1,t_2,\cdots,t_i$ are in $T$, then an addition of a root node $r$
%and arrows connecting each $t_j$ $1 \leq j \leq i$ to $r$ to be
%a child (subtree) of $r$ is also in $T$\\
%
%Use structural induction to prove that the numbers of edges in
%any rooted tree is exactly one fewer than the number of nodes.

\problem \textbf { Induction and Recursive Algorithms}

{\bf Procedure} $binary~search(x,i,j)$\\
$m:=\lfloor(i+j)/2\rfloor$\\
{\bf if} $x=a_m$ {\bf then}\\
$~~~~location:=m$\\
{\bf else if} ($x<a_m$ and $i<m$) {\bf then}\\
$~~~~binary~search$($x,i,m-1$)\\
{\bf else if} ($x>a_m$ and $j>m$) {\bf then}\\
$~~~~binary~search$($x,m+1,j$)\\
{\bf else } $location:=0$

The above procedure searches $x$ in a sequence $a_1,a_2,\ldots,a_n$
(when called with $i=1$, $j=n$).
Prove by (strong) induction that the binary search procedure 
sets $location$ to an index $i$ such that $a_i=x$, if there is such
an index, and otherwise sets $location$ to 0. 

\solution{
\medskip
\textbf{Solution:}\\
Proof by Strong Induction:\\

\textbf{P(n):} The binary search procedure correctly searches a list of length $n$ such that the $location$ variable is set to $i$, where $a_i=x$, if such an index exists, and otherwise $location$ is set to 0.\\

\textbf{Base Case:} P(1) - Calling binary search on an array consisting of one element.  If that element is equal to $x$, then, according to the first \textit{if statement}, $location$ will be set equal to $\lfloor(i+2)/2\rfloor=\lfloor(1+1)/2\rfloor=1$, as desired.  If, however, $a_1 \neq 1$, then since $i$ is not less than $m$ and $j$ is not greater than $m$ ($i=1, j=1, m=1$), the program would go to the final \textit{else statement}, where $location$ gets set to $0$, as desired.\\

\textbf{P(n+1):} To see that this procedure correctly searches a list
of length $(n+1)$, we need only to check that the two \textit{else if
statements} do the correct thing, because they each call binary search
on a smaller array, which, we know by our strong inductive hypothesis,
will get searched correctly.  Now, if the element we are looking for
($x$), is less than $a_m$ and $i<m$ (meaning that there are more
indices to search through), then the procedure gets called again on a
smaller array, that consisting of indices $i$ up to $m-1$.  We already
know the procedure searches this correctly by our strong inductive
hypothesis.  The second \textit{else if statement} does the same thing
if $x$ is bigger than our current element ($x>a_m$), and there is more
of the array to search through ($j>m$).  Therefore, the procedure
correctly calls itself on a smaller array, which by P(n) we know does
the correct search.  Therefore, we have show that $P(1)\vee P(2)\vee
P(3)\vee \ldots \vee P(n) \implies P(n+1)$, and our proof by strong
induction is complete.  }


\newpage

\problem \textbf{Relations}

\begin{problemparts}

\ppart Consider the following putative theorem and the accompanying proof.

\begin{theorem*}
  For any sets $A$, $B$, $C$, and $D$, if $A \times B \subseteq C
  \times D$ then $A \subseteq C$ and $B \subseteq D$.
\end{theorem*}

\begin{proof}
  Suppose $A \times B \subseteq C \times D$.  Let $a$ be an arbitrary
  element of $A$, $b$ be an arbitrary element of $B$, and $(a, b) \in
  A \times B$.  Since $A \times B \subseteq C \times D$, it follows
  that $(a, b) \in C \times D$.  Therefore, $a \in C$ and $b \in D$.
  Since $a$ and $b$ were arbitrary elements of $A$ and $B$,
  respectively, this shows that $A \subseteq C$ and $B \subseteq D$.
\end{proof}

Is the proof correct?  If so, what proof strategies does it use?  If
not, can it be fixed?  Is the theorem correct?

\solution{
\medskip
\textbf{Solution:}\\
    The problem lies in the statement \emph{``let $a$ be an arbitrary
      element of $A$''} (and without loss of generality, $b$ an
    arbitrary element in $B$).  Namely, if $A = \emptyset$, $B = \{1,
    2, 3\}$, $C = \{1, 2\}$, and $D = \{3, 4\}$, then $A \times B
    \subseteq C \times D$ ($\emptyset \subseteq E$ for any set $E$),
    but $B \not\subseteq D$.  This is an example of the proof failing
    at a boundary case.
  }

%%%%%%%%%% PROBLEM %%%%%%%%%

\ppart
Let $A$ be the adjacency matrix for a digraph $G$ with $n$ vertices.  Note
that $A$ is a zero-one valued $n \times n$ matrix.  In this problem we use
the Boolean ``OR'' operation, $\vee$, instead of ``+'' when multiplying
zero-one valued matrices (this is called ``boolean'' matrix product).


(i) For $k \in \naturals$, let $A^k$ be the $k$th {\em Boolean} power
of $A$.  Prove that ${A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertex of $G$.

\solution{
    \medskip
	\textbf{Solution:}\\
    Let $P(n)$ be the predicate that $A^{n}_{ij} = 1$ iff there is a
    directed path of length $n$ from the $i$th to the $j$th vertex
    of $G$.  We prove that $P(n)$ holds for all $n\geq 1$ by induction
    on $n$.

    {\bf Inductive Hypothesis:} $P(k): A^{k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex
    of $G$.
 

    {\bf Base Case:} $k = 1$.  By the definition of an adjacency matrix
    $A$, $A_{ij} = 1$ iff there is a directed edge (directed path of
    length $k = 1$) from the $i$th to the $j$th vertex of $G$.
 

    {\bf Inductive Step:} Assume $P(k)$ to prove $P(k+1)$.
 
\[A^{k}_{ij} = \bigvee_{l \in G} (A^{k}_{il} \wedge A_{lj})\]

Now we consider both directions for the iff.

Case 1:

There is a directed path of length $k+1$ from the $i$th to the $j$th
vertex of $G$.  This path looks like $i, i_1, i_2, \dots i_k, j$.
Then consider $l = i_k$.  $A^{k}_{il} = 1$ (inductive hypothesis).
${A}_{lj} = 1$ (there is an edge from $i_k$ to $j$), under the Case 1
assumption.  Therefore,

\[({A^k}_{il} \wedge A_{lj}) = 1\]
\[{A^{k+1}}_{ij} = 1\]

Case 2: $A^{k+1}_{ij} = 1$.

Then $\exists\; l \in G : (A^{k}_{il} \wedge A_{lj}) = 1$.  Thus there
is an edge from $l$ to $j$ and there is path of length $k$ from $i$ to
$l$(by the inductive hypothesis) which looks like $i, i_1, i_2, \dots
i_{k-1}, l$.  Thus, there is a path of length $k+1$ from $i$ to $j$
which hits $l$ on the $k$th step and then has the $k+1$st edge from
$l$ to $j$.  This path follows the vertices: $i, i_1, i_2, \dots
i_{k-1}, l, j$.

Q.E.D.
}


(ii) Let $B = A \vee I$ where $I$ is the $n \times n$ identity matrix.
Prove that $B^{k}_{ij} = 1$ iff there is a directed path of length
$\leq k$ from the $i$th to the $j$th vertex of $G$.

\solution{
\medskip
\textbf{Solution:}\\
    From part a, it can be seen that $B^{k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex of
    $G'$, where $G'$ is the graph described by the adjacency matrix
    $B$.  Since $G'$ is just $G$ with self loops, a path exists
    between $i$ and $j$ in $G'$ iff a path exists between $i$ and $j$
    in $G$ (all vertices have paths of length $0$ to themselves).

    For any such path between $i$ and $j$ in $G'$, either it uses a
    self-loop edge or it does not.  If it does not, then the
    equivalent path in $G$ will have the same length.  If it does,
    then there is a shorter path in $G$ which can be obtained by not
    using the self loop.  So if there is a path of length $k$ between
    $i$ and $j$ in $G'$ then there is a path of length $\leq k$
    between $i$ and $j$ in $G$.

    If there is a path of length $\leq k$ between $i$ and $j$ in $G$,
    then it can be made to be of length $k$ by using self loops to
    lengthen the path.  Thus there is a path in $G'$ of length $k$ iff
    there is a path in $G$ of length $\leq k$.  Since $B^{k}_{ij} = 1$
    iff there is a path of length $k$ between $i$ and $j$ in $G'$ then
    $B^{k}_{ij} = 1$ iff there is a path of length $\leq k$ between
    $i$ and $j$ in $G$.
    }

(iii) Conclude that $B^{n}_{ij} = 1$ iff there is a directed path from
the $i$th to the $j$th vertex.  

\solution{
\medskip
\textbf{Solution:}\\
If $B^{n}_{ij} = 1$ then there is a directed path from the $i$th to
the $j$th vertex.  If $B^{n}_{ij} = 0$ then there is no path of length
less than or equal to $n$ from the $i$th to the $j$th vertex.  There must also be no path of
length greater than $n$ from the $i$th to the $j$th vertex.  If there were, then the
path must cross through some vertices twice, since the length of the path is
greater than $n$.  For those vertices through which the path passes
twice, eliminate 
the loops so that the path uses no vertex more than once.  This means the
path must be of length less than or equal to $n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length less than or equal
to $n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\
}

\end{problemparts}



\problem \textbf{Equivalence Relations}
Let $(a,b) \sim (c,d)$ if $a+d = b+c$. We claim that $\sim$ is an
equivalence relation.

\begin{problemparts}

\problempart Partition the set $\{0,1,2\} \times \{0,1,2\}$ 
into the distinct equivalence classes under $\sim$.

\solution{
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}
}

\problempart  Prove that $\sim$ is an equivalence 
relation on $\integers \times \integers$.

\solution{
\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.
}

\problempart 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.

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


\end{document}

%%%%%%%%%% PROBLEM %%%%%%%%%

%\newpage
\problem \textbf{Scheduling Courses}
% source: fall98/tutorials/H19-rec4.tex, beginning

We consider a simple kind of scheduling problem --- for MIT courses with
prerequisites.  The problem is to determine how a student could complete
all of the courses in the fewest terms, under the simplifying, if
unlikely, assumption that there is no limit on the number of courses a
student can take in a term as long as their prerequisites have all been
met.  We model this problem with a digraph.  An example is shown in
Figure~\ref{fig:dag}.

\begin{figure}[htbp!]
	%graphic is from  /a/class/6.042/spring00/archive/lectures/
 \centerline{\resizebox{!}{2.0in}{\includegraphics{../handouts/figures/dag}}}

  \caption{This is a picture of a directed acyclic graph.  Vertices
    are labeled with course numbers.  An edge from $u$ to $v$
    indicates that course $u$ is a prerequisite for course $v$.}

  \label{fig:dag}
\end{figure}

\problempart What's the length of a critical path; find such a path.
\problempart  How many terms are necessary and sufficient to complete all of the
courses in Figure~\ref{fig:dag}, assuming prerequisites are observed,
but course load is no issue? Prove your answer (both necessary and sufficient).

\solution{
\medskip
\textbf{Solution:}\\
The answer is suggested by the way Figure~\ref{fig:dag} is drawn.
Each term the student could take all the courses in a horizontal row,
starting with the first row and working down.  All of the courses in
each row are incomparable, and all the necessary prerequisites are in
previous rows.  Since there are six rows, the student can finish in
six terms.

Furthermore, there is no way to finish in fewer than six terms, since each
term the student can take at most one course in the six-course sequence
18.01, 18.03, 6.002, 6.004, 6.033, 6.857.  Notice that this sequence
constitutes the longest directed path in the graph.
}

%\problempart Show that there is a schedule for taking courses
%which achieves the minimum number of terms, $t$.  
%the previous question includes this direction

\solution{
\medskip
\textbf{Solution:}\\
    The solution to the previous part implies that $t$ terms are
    sufficient.  In term $i$, the student should take the set of
    courses in the $i$th block.  Since the edges into any block come
    from an earlier block, all the prerequisites of courses in a block
    have been taken by the time the block is scheduled to be taken.
    And since the blocks partition the set of all courses, the student
    will complete every course.
  }


