\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

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

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
  \typeout{}
  \typeout{Solutions *INCLUDED*.} 
  \newcommand{\reading}[1]{}
  \newcommand{\omitsolution}[1]{#1}
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
%
  \newcommand{\handoutlabel}{sol3}
  \newcommand{\handouttitle}{Problem Set 3 Solutions}
  \newcommand{\handoutdate}{February 24, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\reading}[1]{#1\vfill\mbox{}\newpage}
  \newcommand{\omitsolution}[1]{}
%
  \newcommand{\handoutlabel}{ps3}
  \newcommand{\handouttitle}{Problem Set 3}
  \newcommand{\handoutdate}{February 15, 2000}
  \newcommand{\duedate}{February 24, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{\pset{3}{\handoutdate}{2:35pm in lecture, \duedate}}
%
\fi

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

\begin{document}

%\handout{\handoutlabel}{\handouttitle}{\handoutdate}

%\pset{3}{February 15, 2000}{2:35pm in lecture, February~24, ~2000}

\titlebar


\reading{%

\textbf{Self-Study Reading:}%
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
  Sections 2.3 up to p. 122
\item[Velleman, \textit{How to Prove It}:] \mbox{} \\ %
  1.4--1.5, 2.3.
\end{description}

\textbf{Note:} The self-study reading covers basic mathematical topics
that we assume you are familiar with and that will not be explicitly
covered in the lectures.  We recommend that you skim them over and
encourage you to discuss any topics that are unclear to you with your
TA during the weekly tutorial.

\bigskip

\hrule
\vspace*{0.5\baselineskip}

\textbf{Self-Study Problems:}%
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
  Section 2.3, exercises 1, 5, 7, 9, 11, 15, 29, 31, 33, 35, 37
\item[Velleman, \textit{How to Prove It}:] \mbox{} \\ %
  Section 4.2, Exercises 3, 5
  Section 4.3, Exercise 2
  Section 4.4, Exercise 1
  Section 4.5, Exercise 6
  Section 4.6, Exercise 3
\end{description}

\textbf{Note:} The self-study problems are intended for you to get
some practice on the mathematical topics covered by the self-study
reading.  Again, make sure that you understand the concepts presented
in the problems and that you discuss any topics that are unclear to
you with your TA during the weekly tutorial.

\bigskip

\hrule
\vspace*{0.5\baselineskip}

\textbf{Reading:}
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
  Well-Ordering: Section 3.2; 
%  Structural Induction: ???; 
  Recursive Definitions: Section 3.3;
  Relations and Graphs: Ch. 6, Ch. 7
\item[Velleman, \textit{How to Prove It}:] \mbox{} \\ %
  Well-Ordering: Section 6.4;
%  Structural Induction: ???;
  Recursive Definitions: Section 6.3;
  Relations and Graphs: Sections 4.1--4.6
\end{description}

}

\textbf{Required Problems:}

\vspace*{0.5\baselineskip}

\collaboration

%%%%%%%%%%%% BEGIN PROBLEMS %%%%%%%%%%%

\problem 
% topic: Cartesian products, disjoint, direct proof
% source: Velleman 4.1.8

Prove that for any sets $A$, $B$, $C$, and $D$, if 
$A \times B$ and $C \times D$ 
are disjoint, then either $A$ and $C$ are disjoint or $B$ and $D$ are disjoint.

\omitsolution{%
\begin{solution}

We will prove the contrapositive.  In other words,
\newline 
prove: 
$[(A \intersect C) \neq \emptyset \land (B \intersect D) \neq \emptyset] 
\implies [(A \times B) \intersect (C \times D) \neq \emptyset]$
\newline
assume:
$[(A \intersect C) \neq \emptyset \land (B \intersect D) \neq \emptyset]$
\newline
$\therefore \exists a (a \in A \land a \in C) \land 
\exists b (b \in B \land b \in D)$.
\newline
then, $(a, b) \in A \times B$   by definition of Cartesian product, 
Velleman 158.
\newline
and, $(a, b) \in C \times D$   by definition of Cartesian product, 
Velleman 158.
\newline
$\therefore (a, b) \in [(A \times B) \intersect (C \times D)]$ so 
$[(A \times B) \intersect (C \times D) \neq \emptyset]$
\newline
$QED$

\end{solution}
}

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


\problem Find the flaws in the following fallacious proofs of
putative theorems.  For each, if the theorem is false, give a
counterexample; if it is correct, give a correct proof.

%\begin{problemparts}

\problempart
% topic: false proof, Cartesian products, relations
% source: Velleman 4.1.5


\emph{Theorem?} For any sets $A$, $B$, $C$, and $D$, $(A \union C)
\times (B \union D) \subseteq (A \times B) \union (C \times D)$?

\begin{proof}
  Suppose $(x, y) \in (A \union C) \times (B \union D)$.  Then $x \in A \union 
  C$ and $y \in B \union D$, so either $x \in A$ or $x \in C$, and either 
  $y \in B$ or $y \in D$.  We consider these cases separately.

  \emph{Case 1}. $x \in A$ and $y \in B$.  Then $(x, y) \in A \times B$.
  \newline
  \emph{Case 2}. $x \in C$ and $y \in D$.  Then $(x, y) \in C \times D$.

  Thus, either $(x, y) \in A \times B$ or $(x, y) \in C \times D$, so 
  $(x, y) \in (A \times B) \union (C \times D)$.
\end{proof}

\omitsolution{%
\begin{solution}
\newline
\textbf{The theorem does not hold.}
The cases do not exhaust all of the
possibilities.
The correct way to write the proof would be to include first the possibilities
that $A$, $B$, $C$, and $D$ are null and then trying out all \emph{four} 
cases, $x \in A \land y \in B$, $x \in A \land y \in D$, $x \in C \land y \in 
B$, and $x \in C \land y \in D$.
\newline
Consider the case where $A = \emptyset$, $C = \{1\}$, $B = \{2\}$, and $D = 
\{4\}$.  Then, the LHS (left-hand-side) gives $\{(1, 2), (1, 4)\}$, while the
RHS gives $\{(1, 4)\}$.  The statement of the theorem clearly does not hold in
this case.

\end{solution}
}

\problempart
% topic: ???
% source: Velleman 4.3.10

\emph{Theorem?}  Suppose $R$ is a relation on $A$.  If $R$ is symmetric and 
transitive, then $R$ is reflexive.

\begin{proof}
Let $x$ be an arbitrary element of $A$.  Let $y$ be any element of $A$ such 
that $xRy$.  Since $R$ is symmetric, it follows that $yRx$.  Then by 
transitivity, since $xRy$ and $yRx$.  We conclude that $xRx$.  Since $x$ was
arbitrary, we have shown that $\forall x \in A (xRx)$, so $R$ is reflexive.
\end{proof}

\omitsolution{%
\begin{solution}
\newline
\textbf{The theorem does not hold.}
Suppose $A = \{a, b, c, d\}$ and we are given the relation 
$R = \{(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), 
(c, c)\}$.  Then R is symmetric [``$\forall x \in A \forall y \in A (xRy 
\implies yRx$''] and transitive [``$\forall x \in A \forall y \in A 
\forall z \in A ((xRy \land yRz) \implies xRz)$''].  However, it is not
reflexive, as it is not the case that ``$\forall x \in A (xRx)$'', as 
$(d, d) \notin R$.
\end{solution}
}


\problempart
% topic: relations, building posets out of transitive closure of a reflexive, 
%        antisymmetric relation
% source: Velleman 4.5.12

\emph{Theorem?}  Suppose $R$ is a reflexive, antisymmetric relation on $A$.  
Let $S$ be the transitive closure of $R$.  Then $S$ is a partial order on $A$.
\begin{proof}
$R$ is already reflexive and antisymmetric.  To form the relation $S$ we add 
more ordered pairs to make it transitive as well.  Thus, $S$ is reflexive, 
antisymmetric, and transitive, so it is a partial order.
\end{proof}

\omitsolution{%
\begin{solution}
\newline
\textbf{The theorem does not hold.}
Suppose we have the relation $R = \{(a, a), (b, b), (c, c), (a, b), 
(b, c), (c, a)\}$.  This relation is both reflexive and antisymmetric
on $A = \{a, b, c\}$.  However, taking its transitive closure would break
the antisymmetry.  For example, the transitive closure $T$ of $R$ includes 
$(a, c)$, since there is a walk from $a$ to $c$ in $R$.  Since $T$ also 
contains $(c, a)$, it is not antisymmetric.
\end{solution}
}

%\end{problemparts}


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

\problem 
% topic: relations, compositions, reflexive, symmetric, transitive
% source: Velleman 4.3.9

Suppose $R$ and $S$ are binary relations on a set $A$.  For each part, give 
either proofs or counterexamples to justify your answers.

%\begin{problemparts}

\problempart

Suppose $R$ and $S$ are reflexive. Must $R \intersect S$ be reflexive?  What
about $R \union S$?  What about $R^{-1}$?  What about $R \composition S$?

\omitsolution{%
\begin{solution}
\newline
$R \intersect S$: \textbf{Yes.} $\forall a \in R \; (a, a) \land \forall a \in
S \; (a, a)$.  Therefore, $R \intersect S$ contains $(a, a)$ for every 
$a \in A$.
\newline
$R \union S$: \textbf{Yes.} Their intersection contained $(a, a) \forall a \in
A$, so their union does too.
\newline
$R^{-1}$: \textbf{Yes.} For every $(a, a) \in R$, it holds that $(a, a) 
\in R^{-1}$ by the definition of inverse.  Thus, since $\forall a \in A 
(a, a) \in R$, it holds that $\forall a \in A (a, a) \in R^{-1}$, so the 
inverse is reflexive.
\newline
$R \composition S$: \textbf{Yes.} It holds that $\forall a \in A ((a, a) \in
S \land (a, a) \in R)$.  Thus, $\forall a \in A \; \exists b \in A \;
((a, b) \in S \land (b, a) \in R)$, so that $\forall a \in A \; ((a, a) \in 
R \composition S)$ by the definition of composition.
\end{solution}
}

\problempart Suppose $R$ and $S$ are symmetric.  Must $R \intersect S$
be symmetric?  What about $R \union S$?  What about $R^{-1}$?  What
about $R \composition S$?

\omitsolution{%
\begin{solution}
\newline
$R \intersect S$: \textbf{Yes.} If $(x, y) \in R \intersect S$, 
we must prove that $(y, x) \in R \intersect S$.  We have that $xRy$ 
(in which case 
$yRx$ as well) and $xSy$ (in which case $ySx$ as well).  Since $yRx \land
ySx$, we have $(y, x) \in R \intersect S$.
\newline
$R \union S$: \textbf{Yes.} Suppose $(x, y) \in R \union S$.  
Therefore, either $xRy$ (in which case $yRx$ and $\therefore (y, x) \in
R \union S$) or $xSy$
(in which case $ySx$ and $\therefore (y, x) \in R \union S$).  So by 
cases $(y, x) \in R \union S$.
\newline
$R^{-1}$: \textbf{Yes.} Suppose $(x, y) \in R^{-1}$.  By the 
definition of inverse, this 
means that $yRx$.  But since $R$ is symmetric, this means that $xRy$.  By the
definition of inverse again, this means that $(y, x) \in R^{-1}$.  
So $R^{-1}$ is symmetric.
\newline
$R \composition S$: \textbf{No.}  Suppose $A = \naturals$, 
$R = \{(b, c), (c, b)\}$ 
, and 
$S = \{(a, b), (b, a)\}$
.  Then $R \composition S = \{(a, c)\}$, which is not symmetric.
\end{solution}
}

\problempart Suppose $R$ and $S$ are transitive.  Must $R \intersect
S$ be transitive?  What about $R \union S$?  What about $R^{-1}$?
What about $R \composition S$?

\omitsolution{%
\begin{solution}
\newline
$R \intersect S$: \textbf{Yes.} Suppose there is 
a walk from $x$ to $y$ in $R \intersect S$.  We need to prove $(x,y) \in
R \intersect S$.  In order for there to
be a walk from $x$ to $y$ in $R \intersect S$, there must have been a walk 
from $x$ to $y$ 
in both of $R$ and $S$ (otherwise, those walks would not appear in their 
intersection as walks).  Thus, $xRy$ and $xSy$, so $(x, y) \in R 
\intersect S$ as needed.
\newline
$R \union S$: \textbf{No.} Suppose $R = \{(a, b), (b, c), (a, c)\}$ and 
$S = \{(b, c), (c, a), (b, a)\}$.  Then $U = R \union S = \{(a, b), (b, a), 
(b, c), (c, a), (a, c)\}$, so that $cUa$ and $aUb$ but $\neg (cUb)$.
\newline
$R^{-1}$: \textbf{Yes.} Suppose $(a, b) \in R^{-1} \land 
(b, c) \in R^{-1}$.  We must prove that $(a, c) \in R^{-1}$.  
We know from the definition of inverse that
$bRa \land cRb$.  Furthermore, since $R$ is transitive, we have that $cRa$.  
By the definition of inverse again we have that $(a, c) \in 
R^{-1}$, as needed.
\newline
$R \composition S$: \textbf{No.} Suppose $R = \{(b, a), (b, c), (c, a)\}$ and 
$S = \{(a, b), (a, c), (b, c)\}$.  Then $(b, a) \in R \composition S$ and 
$(a, c) \in R \composition S$ but $(b, c) \notin R \composition S$.  
Transitivity fails for the composition. 
\end{solution}
}

\problempart
% topic: equivalence relations, intersection, union, composition
% source: Velleman 4.6.9

Suppose $R$ and $S$ are equivalence relations.  Must $R \intersect S$ 
be an equivalence relation on $A$?  What about $R \union S$?  What about 
$R \composition S$?

\omitsolution{%
\begin{solution}
\newline
$R \intersect S$: \textbf{Yes.}  Here we are supposing $R$ and $S$ are 
reflexive, symmetric, and transitive.  Since we showed above that these 
properties hold over intersection, $R \intersect S$ is reflexive, symmetric,
transitive, and therefore an equivalence relation as well.
\newline
$R \union S$: \textbf{No.}  Suppose $R = \{(a, a), (b, b), (c, c), (a, b),
(b, a)\}$ and 
$S = \{(a, a), (b, b), (c, c), (b, c), (c, b)\}$.  Then $(c, b) \in R \union 
S$ and $(b, a) \in R \union S$ but $(c, a) \notin R \union S$.  Transitivity
fails and $R \union S$ is not an equivalence relation.
\newline
$R \composition S$: \textbf{No.}  Suppose $R$ and $S$ are as in the above 
counterexample.  Then $(a, b) \in R \composition S$ and $(b, c) \in R
\composition S$ but $(a, c) \notin R \composition S$.  Transitivity fails
and $R \composition S$ is not an equivalence relation.
\end{solution}
}

%\end{problemparts}



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

\problem 
% topic: relations, posets
% source: Velleman 4.4.4

Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$.  
Define a relation $T$ on $A \times B$ as follows: $T = \{((a, b), (a', b')) \in
(A \times B) \times (A \times B) \mid aRa' \mbox{ and } bSb'\}$.  Show that $T$ is a partial
order on $A \times B$.  If both $R$ and $S$ are total orders, will $T$ also be 
a total order?

\omitsolution{%
\begin{solution}
\newline
To show $T$ is a poset on $A \times B$, we must show it is reflexive, 
symmetric, and transitive on $A \times B$.
\newline
\emph{Reflexive:} Choose an arbitrary element of $A \times B$, if one exists
(if none exists, there's nothing to prove and $T$ is reflexive).  Call this
element $(x, y)$.  To prove $T$ is reflexive, we must prove $((x, y)T(x, y))$.
Given we have $(x, y)$ chosen, we know $xRx$ and $ySy$ as both $R$ and $S$ 
are reflexive.  Thus, by the definition of $T$, $((x, y), (x, y)) \in T$ as
it is an element of $(A \times B) \times (A \times B)$ such that $xRx \land
ySy$.  Therefore, $T$ is reflexive.
\newline
\emph{Antisymmetric:} We must show that $\forall (a, b) \in (A \times B) \;
\forall (c, d) \in (A \times B) \; 
(((a, b)T(c, d) \land (c, d)T(a, b)) \implies (a, b) = (c, d))$.  Suppose 
we choose an arbitrary $a \in A$, $b \in B$, $c \in A$, and $d \in B$ such 
that the above premise holds.  If no such elements exist, $T$ is trivially
antisymmetric.  We have that $aRc \land cRa$ from the definition of $T$,
and thus $a = c$ as $R$ is antisymmetric.  Furthermore, $b = d$ by similar
rationale.  Thus, $(a, b) = (c, d)$, as needed.  $T$ is antisymmetric.
\newline
\emph{Transitive:} We must show that $\forall (a, b) \in (A \times B) \; 
\forall (c, d) \in (A \times B) \; \forall (e, f) \in (A \times B) \; 
(((a, b)T(c, d) \land (c, d)T(e, f)) \implies (a, b)T(e, f))$.  Let's 
arbitrarily choose a particular $a \in A$, $b \in B$, $c \in A$, $d \in B$, 
$e \in A$, and $f \in B$ such that the premise of the above implication holds. 
If there are no such elements, there is nothing to prove and $T$ is transitive.
We know that since $aRc$ and $cRe$ (by the definition of $T$), $aRe$ (by the
definition of $R$ being transitive).  Similarly, $bSf$ as $S$ is transitive.  
But since $aRe \land bSf$, $((a, b), (e, f)) \in T$ by the definition of $T$. 
Therefore, $T$ is transitive.
\newline
\textbf{No, $T$ is not a total order.}  Suppose you have $R = 
\{(a, a), (a, b), (b, b)\}$ (lexicographically less than or equal to) and 
$S = \{(1, 1), (1, 2), (2, 2)\}$ (numerically less than or equal to).  Then 
if we form $T$ as defined, there is no way to compare the points $(b, 1)$
and $(a, 2)$.
\newline
%\emph{A picture here would be nice!!!}
\end{solution}
}

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

\problem 
% topic: relations, transitive closures, symmetric relations
% source: Velleman 4.5.10

Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$.
Prove that if $R$ is symmetric, then so is $S$.  (Hint:  Assume that $R$ is 
symmetric.  Prove that $R \subseteq S^{-1}$ and $S^{-1}$ is transitive.  What
can you conclude about $S$ and $S^{-1}$?)

\omitsolution{%
\begin{solution}
\begin{proof}
Assume that $R$ is symmetric.  We can prove that $R \subseteq S^{-1}$.  
Suppose arbitrary $(a, b) \in R$.  Then $(b, a) \in R$ as well.  So, both 
$(a, b)$ and $(b, a)$ are in $S$ as $R \subseteq S$ by definition of
closure.  Likewise, $(b, a)$ and $(a, b)$ are also in $S^{-1}$ by the 
defintion of inverse.  Thus, $R \subseteq S^{-1}$.
\newline
We must now prove that $S^{-1}$ is transitive.  Suppose we choose an 
arbitrary three elements $a \in A$, $b \in A$, and $c \in A$ such that
$((a, b) \in S^{-1} \; \land (b, c) \in S^{-1})$.  This means that 
$(b, a) \in S \; \land (c, b) \in S$ by definition of inverse.  But 
since $S$ is transitive this means $(c, a) \in S$.  Thus, by definition
of inverse $(a, c) \in S^{-1}$.  This is the necessary condition to 
satisfy transitivity.  Thus, $S^{-1}$ is transitive.
\newline
We know that the cardinality of $S$ and its inverse are both the same.  
Since $S$ was the transitive closure of $R$, it is the smallest set
such that $R \subseteq S$ and $S$ is transitive.  Since $S^{-1}$ has
the same cardinality as $S$, $R \subseteq S^{-1}$, and $S^{-1}$ 
is a transitive superset of (or equal to) $R$; $S^{-1}$ is also a
transitive closure of $R$.  But the transitive closure of $R$ is unique.
So, $S = S^{-1}$.
\newline
Therefore, since $S$ is the same set as its inverse, $S$ is symmetric.  
$QED$. 
\end{proof}
\end{solution}
}


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

\problem 
% topic: relations, special definition ``weakly transitive''
% source: fall98 pset3 Problem 2

A relation $R$ on a set $A$ is {\em weakly
transitive} if for all $a, b, c, d \in A$, the relations $aRb$, $bRc$,
and $cRd$ imply the relation $aRd$.

Prove or disprove the following statements.

%\begin{problemparts}

\problempart Every symmetric, weakly transitive relation is transitive.

\omitsolution{%
\solution{
The claim is false.  The diagram below shows a counterexample.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.0in}{\includegraphics{figures/ps3-relation-cx.eps}}}
\end{figure}
}
}

\problempart Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

\omitsolution{%
\solution{
\begin{proof}
The relation $R$ is an equivalence relation if it is reflexive,
symmetric, and transitive.  The first two properties hold by
assumption; all that remains is to show that $R$ is a transitive
relation.  Suppose that the relations $aRb$ and $bRc$ hold.  Because
$R$ is reflexive, the relation $aRa$ also holds.  Because $R$ is
weakly transitive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}
}
}

%\end{problemparts}

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




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

\problem 
% topic: 
% source: fall98 pset3 Problem 7

Let $G$ and $H$ be undirected graphs with no self-loops.  The {\em
product graph} $P = G \times H$ is defined as follows.  The vertex set
of $P$ is the Cartesian product of the vertex set of $G$ and the
vertex set of $H$.  Thus, each vertex of $P$ is an ordered pair $(v,
w)$ where $v$ is a vertex of $G$ and $w$ is a vertex of $H$.  The
edges in the product graph $P$ are of two types.  First, for every
edge $(v_1, v_2)$ in $G$ and vertex $w$ in $H$, there is an edge
between $(v_1, w)$ and $(v_2, w)$ in $P$.  Second, for every vertex
$v$ in $G$ and edge $(w_1, w_2)$ in $H$, there is an edge between $(v,
w_1)$ and $(v, w_2)$ in $P$.  Note that these two sets of edges are
disjoint.

%\begin{problemparts}

\problempart Draw the product of the two graphs shown below.  
Your diagram must be tidy to receive full credit.  In particular,
label all the vertices, e.g., $(b, 3)$, and use two different colors or
line styles (e.g., dashed and solid) to distinguish the two types of
edge defined above.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1in}{\includegraphics{figures/ps3-twographs.eps}}}
\end{figure}

\omitsolution{%
\solution{
\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figures/ps3-product.eps}}}
\end{figure}
}
}

\problempart Let $G$ be the graph consisting of two vertices connected
by an edge.  Let $G^n$ be the product of $n$ copies of $G$.  Use
induction to prove that $G^n$ has $2^n$ vertices and $n 2^{n-1}$
edges.  (You may assume without proof that the $\times$ operation is
associative.)

\omitsolution{%
\solution{
\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$G^n$ has $2^n$ vertices and $n 2^{n-1}$ edges.  In the base case,
$P(1)$ is true because $G^1$ has $2^1 = 2$ vertices and $1 \cdot
2^{1-1} = 1$ edge.

In the inductive step, for $n \geq 1$ assume that $G^n$ has $2^n$
vertices and $n 2^{n-1}$ edges to prove that $G^{n+1}$ has $2^{n+1}$
vertices and $(n+1) 2^n$ edges.  The remainder of the argument uses
the fact that $G^{n+1} = G^n \times G$.

The vertex set of $G^{n+1}$ is the Cartesian product of the vertex set
of $G^n$ and the vertex set of $G$.  There are $2^n$ vertices in $G^n$
by induction, and there are 2 vertices in $G$ by the definition of the
graph.  Therefore, there are $2^n \cdot 2 = 2^{n+1}$ vertices in
$G^{n+1}$.

The edges of $G^n \times G$ are of two types.  First, for each edge
$(v_1, v_2)$ in $G^n$ and vertex $w$ in $G$, there is an edge between
$(v_1, w)$ and $(v_2, w)$ in $G^{n+1}$.  Thus, the number of edges of
the first type is equal to the number of edges in $G^n$ multiplied by
the number of vertices in $G$, which gives $n 2^{n-1} \cdot 2 = n
2^n$.

Second, for each vertex $v$ in $G^n$ and edge $(w_1, w_2)$ in $G$,
there is an edge between $(v, w_1)$ and $(v, w_2)$ in $G^{n+1}$.
Thus, the number of edges of the second type is equal to the number of
vertices in $G^n$ multiplied by the number of edges in $G$, which
gives $2^n \cdot 1= 2^n$.  Since these two sets of edges are disjoint,
the total number of edges in $G^{n+1}$ is equal to $n 2^n + 2^n =
(n+1) 2^n$.

This shows that $P(n)$ implies $P(n+1)$, and the claim is proved by
induction.
\end{proof}
}
}

%\end{problemparts}

\problem Read the recursive definition of strings over an alphabet
$\Sigma$ in Rosen 3.3, example 10.  Define the {\em reversal} of a
  string $w$, written $w^R$, as follows:
\begin{itemize}
\item $\lambda^R = \lambda$
\item if $w=vx$ where $v \in \Sigma^*$ and $x \in \Sigma$, then $w^R = x v^R$.
\end{itemize}
\nopagebreak Prove that $(vw)^R = w^Rv^R$

\omitsolution{%
\begin{solution}
\begin{proof}
\newline
by \textbf{strong induction} on the length, $n$, of $vw$.
\newline
\begin{tabbing}
XXti\=XXti\=XXti\=XXXXXXXXXXXXXX\=    \kill
\textbf{Base:} vw is of length 0.  Here, $vw = \lambda$ which means $v = w = \lambda$, so $(vw)^R = (\lambda)^R = \lambda = \lambda \lambda = w^Rv^R$.\\
\textbf{Inductive step: Assume:} $P(n): \forall i \in \naturals \; (0 \leq i \leq n) Q(i)$ holds (Inductive Hypothesis).\\
\> That is, $Q(i): ``(vw)^R = w^Rv^R \; for \; an \; arbitrary \; string \; vw \; of \; length \; i''$ \\
We now \textbf{prove} $P(n+1)$ holds.\\
Let $vw$ be an arbitrary string of length $n+1$.\\
\> \textbf{Case 1:} $w$ is of length exactly 0\\
\> \> then $(vw)^R = (v)^R = \lambda v^R = \lambda^R v^R = w^Rv^R$.\\
\> \textbf{Case 2:} $w$ is of length exactly 1\\
\> \> then $v \in \Sigma^*$ and $w \in \Sigma$ ($w$ is a single symbol)\\
\> \> $(vw)^R = wv^R$ by the definition of \emph{reversal}\\
\> \> then $w = w^R$ as $w^R = (\lambda w)^R = w \lambda^R = w$ by definition of \emph{reversal} for a single symbol\\
\> \> so $(vw)^R = w^Rv^R$\\
\> \textbf{Case 3:} $w$ is of length $> 1$ and $\leq n$\\
\> \> then $v \in \Sigma^*$ and has length $\geq 1$\\
\> \> $x \in \Sigma^*$ and $y \in \Sigma$ for some $x$, $y$, s.t. $w = xy$\\
\> \> thus, $vw = vxy$ for some $y \in \Sigma$\\
\> \> let $t = vx$  then, $t \in \Sigma^*$ and is of length $n$ by the definition of \emph{length}\\
\> \> then, $vw = ty$ so that $(vw)^R = (ty)^R = yt^R$ by the definition of \emph{reversal}\\
\> \> we know that $t^R = (vx)^R = x^Rv^R$ by the Inductive Hypothesis at n.\\
\> \> so, $(vw)^R = yx^Rv^R = y^Rx^Rv^R$ by substitution and $y = y^R$ for a single symbol.\\
\> \> we have that $y^Rx^R = (xy)^R = w^R$ by the Inductive Hypothesis at some $i \leq n$\\
\> \> thus, $(vw)^R = w^Rv^R$.\\
\> \textbf{Case 4:} $w$ is of length $n+1$\\
\> \> we have in this case that $v = \lambda$\\
\> \> thus, $(vw)^R = (\lambda w)^R = (w)^R = w^R\lambda = w^R\lambda^R = w^Rv^R$\\
$QED$\\
\end{tabbing}
\end{proof}
\end{solution}
}

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

\problem A pair 6.042 students, Nancy and David,
have decided to devote some of their spare time this term to
establishing dominion over the entire galaxy.  Recognizing this as an
ambitious project, they worked out the following table of tasks on the
back of David's copy of the notes for tutorial 2.

\begin{enumerate}
\item {\bf Devise a logo} and cool imperial theme music - 8 days.
\item {\bf Build a fleet} of Hyperwarp Stardestroyers out of eating
  paraphernalia swiped from Lobdell - 18 days.
\item {\bf Seize control} of the United Nations - 9 days, after task \#1.
\item {\bf Get shots} for Nancy's cat, Muffy - 11 days, after task \#1.
\item {\bf Open a Starbucks chain} for the army to get their caffeine - 10 
days, after task \#3
\item {\bf Train an army} of elite interstellar warriors by dragging
people to see {\em The Phantom Menace} dozens of times - 4 days, after
tasks \#3, \#4, and \#5.
\item {\bf Launch the fleet} of Stardestroyers, crush all sentient
alien species, and establish a Galactic Empire - 6 days, after tasks \#2 and
\#6.
\item {\bf Defeat Microsoft} - 8 days, after tasks \#2 and \#6.
\end{enumerate}

Nancy and David want to complete all these tasks in the shortest
possible time.  However, they have agreed on some constraining work
rules.

\begin{itemize}

\item Only one person can be assigned to a particular task; they can
not work together on a single task.

\item Once a person is assigned to a task, that person must work
exclusively on the assignment until it is completed.  So, for example,
Nancy cannot work on building a fleet for a few days, run get shots
for Muffy, and then return to building the fleet.

\end{itemize}

For each task, the table above lists the time required for completion
and which other tasks must be finished before the given task is begun.

%\begin{problemparts}
\problempart Express the information in the task list using some type
of graph (label the vertices to reflect task lengths).

\omitsolution{%
  \solution{%
    The information in the table is represented in the
    Figure~\ref{fig:tasks} in the form of a directed acyclic graph.
    Each vertex represents a task, and the weight of a vertex is the
    completion time.  Each directed edge represents a dependency
    between tasks.

    \begin{figure}[htbp]
      \centerline{\resizebox{!}{3.0in}{\includegraphics{figures/ps3-p9.eps}}}
      \caption{Graph representing the task precedence constraints.}
      \label{fig:tasks}
    \end{figure}
    }
  }

\problempart Give some valid order in which the tasks might be completed.

\problempart Nancy and David want to know how long conquering the
galaxy will take.  David suggests dividing the total number of days of
work by the number of workers, which is two.  What lower bound on the
time to conquer the galaxy does this give, and why might the actual
time required be greater?

\omitsolution{
\begin{eqnarray*}
\frac{8 + 18 + 9 + 11 + 10 + 4 + 6 + 8}{2} & = & 37 \text{ days}
\end{eqnarray*}

If working together and interrupting work on a task were permitted,
then this answer would be correct.  However, the rules may prevent
Nancy and David from both working all the time.}

\problempart Nancy proposes a different method for determining the
duration of their project.  She suggests looking at the duration of
the ``critical path'', the longest sequence of tasks such that each
depends on the one before.  What lower bound does this give, and why
might it also be too low?

\omitsolution{The longest sequence of tasks is devising a logo (8 days),
seizing the U. N. (9 days), opening a Starbucks (10 days), training the 
army (4 days), and then
defeating Microsoft (8 days).  Since these tasks must be done
sequentially, galactic conquest will require at least 39 days.

If there were enough workers, this answer would be correct; however,
with only two workers, Nancy and David may be unable to make progress
on the critical path every day.}

\problempart What is the minimum number of days that Nancy and David
need to conquer the galaxy?  No proof is required.

\omitsolution{
40 days.  Tasks could be divided as follows:
\newline
David: \#1 (days 1-8), \#3 (days 9-17), \#4 (days 18-28), \#8 (days 33-40).
\newline
Nancy: \#2 (days 1-18), \#5 (days 19-28), \#6 (days 29-32), \#7 (days 33-38).
\newline

}

%\end{problemparts}

%%%%%%%%%%%% END PROBLEMS %%%%%%%%%%%

\end{document}

\endinput 

%%%%%%%%%%%%%% NOT READ %%%%%%%%%%%%%


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

\problem 
% topic: relations, compositions, domains, ranges
% source: Velleman 4.2.7

Suppose $R$ is a relation from $A$ to $B$ and $S$ and $T$ are relations from 
$B$ to $C$.  Must the following statements be true?  Justify your answers with
proofs or counterexamples.

%\begin{problemparts}

\problempart
If $S \subseteq T$ then $S \composition R \subseteq T \composition R$.

\omitsolution{%
\begin{solution}

\emph{not done yet}

\end{solution}
}

\problempart
$(S \intersect T) \composition R \subseteq (S \composition R) \intersect
(T \composition R)$.

\omitsolution{%
\begin{solution}

\emph{not done yet}

\end{solution}
}

\problempart
$(S \intersect T) \composition R = (S \composition R) \intersect
(T \composition R)$.

\omitsolution{%
\begin{solution}

\emph{not done yet}

\end{solution}
}

\problempart
$(S \union T) \composition R = (S \composition R) \union
(T \composition R)$.

\omitsolution{%
\begin{solution}

\emph{not done yet}

\end{solution}
}

%\end{problemparts}








\begin{fminipage}
{\bf Remember} to include a \emph{collaboration statement} on the
front page of your solutions.  \\
(See Handout 1, \emph{Course Information}.)
\end{fminipage}






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

\problem 
% topic: structural induction
% source: fall99 pset2

Suppose we start with a sequence of fully parenthesized arithmetic or
Scheme expressions, and then erase all the alphanumeric characters other
than parentheses.  The result is a string of parentheses which ``match
up''.

For example, erasing non-parenthesis characters from the expression
\texttt{(if (or x y) u v)} leaves the string \texttt{(())}.  Similarly,
erasing non-parentheses from the sequence of three arithmetic expressions
\[
\texttt{(x * x), (y + (3 * (z - 9))), ((x + y) * (u + w))}
\]
leaves the string
\[
\texttt{()((()))(()())}.
\]
On the other hand, even though the string \texttt{())(()} has an equal
number of left and right parentheses, it cannot be obtained by erasing in
this way---because the two middle parentheses don't match up.  Also, no
string of parentheses which begins with a right parenthesis or ends with a
left parenthesis can match up.

We can give an inductive definition of the set, SMU, of ``Strings that
Match Up'', as follows:

\begin{itemize}
\item The empty string (consisting of no parentheses) is an SMU.

\item If $s$ and $t$ are SMU's, then the string $\texttt{(}s\texttt{)}t$
is an SMU.  That is, the new string starts with a left parenthesis which
is followed by the parenthesis characters in the string $s$, followed by a
right parenthesis, followed by the parenthesis characters in the string
$t$.

\item No other strings are SMU's.

\end{itemize}


There is a simple test to determine whether a string of parentheses is an
SMU: starting with zero, read the string from left to right adding one for
each left parenthesis and -1 for each right parenthesis.  A string
\emph{counts well} when the count never goes negative and is back to zero
by the end of the string.  Let CW be the set of strings of parentheses
which Count Well.

%\begin{problemparts}

\problempart
Prove that CW contains SMU.

\omitsolution{%
\solution{We prove by induction on the definition of SMU (that is,
structural induction) that every element of SMU counts well, so SMU is
contained in CW.  The induction hypothesis is
\[
P(s) ::\equiv s \in \mbox{CW}.
\]
\begin{proof}

{\bf Base Case}: $P(\mbox{empty string})$ holds since the count of the
empty string ends when it starts at zero.

{\bf Inductive Step:} Assume $P(s)$ and $P(t)$ are true.  We need to show
that $P(\texttt{(}s\texttt{)}t)$ is true.

The count values for $\texttt{(}s\texttt{)}t$ start with 0.  Reading the
initial left parenthesis yields 1 as the next count value.  This 1 serves
as the start of a series of count values exactly equal to the count values
of $s$, with each value incremented by one.  Since $s \in \mbox{CW}$ by
hypothesis, these incremented count values begin with 1, always stay
positive, and end with 1.  The right parenthesis immediately after $s$
reduces the ending count to 0.  This 0 serves as the start of the
remaining count values which are exactly the count values of $t$.  Since
$t \in \mbox{CW}$, these remaining values never go negative and end at 0.
Hence the entire sequence of count values for $\texttt{(}s\texttt{)}t$
starts with 0, never goes negative, and ends with 0, which proves that
$\texttt{(}s\texttt{)}t \in \mbox{CW}$.
\end{proof}}
}

\problempart
Conversely, prove that SMU contains CW.

\omitsolution{%
\solution{We show that every string $r\in \mbox{CW}$ is an SMU by
strong induction on the length of $r$.  The induction hypothesis is
\[Q(n) ::\equiv \forall r \in \mbox{CW}(\mbox{if $r$ is length $n$, then
$r \in \mbox{SMU}$}).\]
\begin{proof}

{\bf Base Case} $n = 0$: In this case there is only one string of length
$n$, namely the empty string, which is in SMU by definition, proving
$Q(0)$.

{\bf Inductive Step:} Assume that $Q(k)$ is true for all $k\leq n$, we
need to prove that $Q(n+1)$ is also true.

So suppose $r$ is a length $n+1$ string that counts well.  We must prove
that $r \in \mbox{SMU}$.

Now since $r$ counts well, it must start with a left parenthesis (or else
the count would immediately go negative).  Likewise, since the count for
$r$ returns to the value 0 by the end, $r$ must end with right
parenthesis.  So there must be a \emph{first} right parenthesis in $r$
after which the count returns to 0.  Let $s$ be the substring of $r$
between the initial left parenthesis and this right parenthesis.  So
\[
r = \texttt{(}s\texttt{)}t
\]
for some string $t$.

Since counts only change by one as each parenthesis character is read, and
the count for $r$ \emph{first} returns to 0 after the right parenthesis
following $s$, the count during $s$ must start and end with 1 and must
stay \emph{positive} in between.  But this implies that a count for $s$
alone, which would start with 0, would also end with 0 and stay
\emph{nonnegative} in between.  That is, $s$ by itself counts well.  Since
the length of $s \in \mbox{CW}$ is less than the length of $r$, we have by
strong induction that $s \in \mbox{SMU}$.

Further, we know the count for $r$ returns to 0 after the right
parenthesis following $s$, and since $r \in \mbox{CW}$, the count ends
with 0 again and stays nonnegative in between.  But this implies that $t$
counts well, and since the length of $t$ is less than the length of $r$,
we have by strong induction that $t \in \mbox{SMU}$.  Now by the second
case in the definition of SMU, we conclude $\texttt{(}s\texttt{)}t$,
namely $r$, is in SMU.
\end{proof}}
}

%\end{problemparts}

