\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{textcomp} % to get \textcent
\usepackage{epsfig}

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document} 
\inclassproblems{4, Wed.}                    % !! start the paper


%-----------------------------------------------------------------%
% F01 Practice probs 3
% Source: Velleman Sec 4.2, Exercise 3 parts a,b and c.\\
% Used by Karger Spring 01, but changed sets slightly (Rad)

\begin{problem}
Let
\begin{eqnarray*}
A & \eqdef & \set{1,2,3},\\
B & \eqdef & \set{4,5,6},\\
R & \eqdef & \set{(1,4), (1,5), (2,5), (3,6)},\\
S & \eqdef & \set{(4,5), (4,6), (5,4)}.
\end{eqnarray*}
Note that $R$ is a binary relation between $A$ and $B$, that is, $R \subseteq A
\cross B$.  Also, $S$ is a binary relation on $B$, that is, $S \subseteq B
\cross B$.

List the ordered pairs, write the matrix, and draw the directed graph
representing  each of the following relations:
\bparts
\ppart $S\circ R$

\solution{\mbox{}\\
\begin{center}
$\set{(1,5), (1,6), (1,4), (2,4)}$
\qquad
\begin{tabular}{c|ccc} 
  & 4 & 5 & 6 \\\hline
1 & 1 & 1 & 1 \\
2 & 1 & 0 & 0 \\
3 & 0 & 0 & 0 
\end{tabular}
\qquad
\parbox[c]{0.25\textwidth}{\resizebox{!}{1.5in}{
   \includegraphics{figures/rel-composition1.pdf}}}
\end{center}
\vspace*{-3.5em}
}

\ppart $S\circ S$

\solution{\mbox{}\\
\begin{center}
$\set{(4,4), (5,5), (5,6)}$
\qquad
\begin{tabular}{c|ccc} 
  & 4 & 5 & 6 \\\hline
4 & 1 & 0 & 0 \\
5 & 0 & 1 & 1 \\
6 & 0 & 0 & 0 
\end{tabular}
\qquad
\parbox[c]{0.25\textwidth}{\resizebox{!}{1.5in}{
   \includegraphics{figures/rel-composition2.pdf}}}
\end{center}
\vspace*{-3.5em}
}

\ppart $S^{-1}\circ R$

\solution{\mbox{}\\
\begin{center}
$\set{(1,5), (1,4), (2,4), (3,4)}$
\qquad
\begin{tabular}[c]{c|ccc} 
  & 4 & 5 & 6 \\\hline
1 & 1 & 1 & 0 \\
2 & 1 & 0 & 0 \\
3 & 1 & 0 & 0 
\end{tabular}
\qquad
\parbox[c]{0.25\textwidth}{\resizebox{!}{1.5in}{
   \includegraphics{figures/rel-composition3.pdf}}}
\end{center}
\vspace*{-3.5em}
}

\eparts

\end{problem}

\iffalse

\begin{problem}
Let $R$ be the relation on the set $A=\{2,3,4,5,6,7,8\}$ such that
\[
a\,R\, b \ \ \text{iff} \ \ [a\mbox{ is prime} \land (a\divides b)]
\]
(where $a\divides b$ means that $a$ divides $b$).

\begin{problemparts}

\problempart
List the ordered pairs, write the matrix, and draw the directed graph representing $R$.
\solution{
(2,2) (2,4) (2,6) (2,8) (3,3) (3,6) (5,5) (7,7)

\[
M_R = 
\left( \begin{array}{ccccccc}
        1 & 0 & 1 & 0 & 1 & 0 & 1\\
        0 & 1 & 0 & 0 & 1 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0\\
        0 & 0 & 0 & 1 & 0 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 1 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0
       \end{array}
\right)
\]

\begin{figure}[h]
\centerline{\includegraphics[height=2.5in]{figures/digraph-ps2f03.pdf}}
\end{figure}

}

\problempart Which of the following properties does $R$ have: reflexive,
symmetric, antisymmetric, transitive?  Explain.

\solution{$R$ is not reflexive or symmetric.  It is antisymmetric and transitive.}

\end{problemparts}

\end{problem}
\fi

%F01 PS3
% Problem Repository, only used two parts (Rad)
% source: spring00 ps3, Velleman 4.3.9 
% topic: relations, compositions, reflexive, symmetric, transitive

\begin{problem}
Suppose $R$ and $S$ are binary relations on a set, $A$.  Suppose $R$ and
$S$ are symmetric.  For each of the following relations, either prove it
is symmetric or give a counterexample showing that it may not be.
\begin{itemize}
\item $R \intersect S$
\item $R \union S$
\item $R \composition S$
\end{itemize}

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

$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$.

$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.

$R \composition S$: \textbf{No.}  Suppose $A = \{a,b,c\}$, $R = \{(b, c),
(c, b)\}$ , and $S = \{(a, b), (b, a)\}$ .  Then $R \composition S = \{(a,
c)\}$, which is not symmetric.

} %end solution
\end{problem}


%%CP3F F02

% Made this up (RAD)
% based on Bassethound problem from last year (fall 01, pset3)
\instatements{\newpage}
\begin{problem}

Recently MIT students have been taking a hard look at the haphazard
building layout, and have been asking some hard questions. As always
they know they can use their superior mathematical skills to get some
real answers to those hard questions.

They decide to express the MIT building layout as a relation. Let $C$
be the set of all building numbers and let $R$ be the relation on the
set $C$ such that $(a,b) \in R$ if building $a$ and building $b$ are
physically adjacent and there is a door between $a$ and $b$ (more
importantly, one doesn't have to go outside to get from $a$ to
$b$). Note that if $(a,b) \in R$, then $(b,a)$ is also in $R$, so $R$
is a symmetric relation. For convenience, they also define a building
to be related to itself, so $(a,a) \in R$.

\begin{problemparts}

\problempart For this part only, let $C$ be the set of MIT buildings
10,13,12,4,8,26. Then $R$ looks like this:
\begin{center}
\vspace*{-6em}
\resizebox{!}{3.5in}{
   \includegraphics{figures/MITbuildings.pdf}}
\vspace*{-6em}
\end{center}
%\input{figures/cp3F-figure1.latex}
% \begin{verbatim}
%                    26
%         13   12    |
%         |    |     |
%         10---4-----8
% \end{verbatim}
Compute $R^2 = R \circ R$. \newline
Compute $R^3 = R \circ R^2$.

\solution{
$R^2$ consists of all pairs of buildings that are connected via exactly
one building. Since there are self-loops in the connectivity graph (each
building is connected to itself), $R^2$ includes everything which is in
$R$ as well. For example, $(13,10)$ which is in $R$ must also be in
$R^2$ because you can go from building $13$ to building $10$ ``via one
building'' by just going around building $13$ once and then moving on to
building $10$. That said, we conclude that
\[R^2 = R \union \Big\{(13,4),(4,13),
(10,12),(12,10),(10,8),(8,10),(12,8),(8,12),(4,26),(26,4)\Big\}
\]

Similarly, $R^3$ contains everything which is in $R^2$ (because of the
self-loops), plus all the extra pairs that we get by allowing
connections via \emph{two} intermediate buildings. So we have:$$R^3=
R^2 \union
\Big\{(13,12),(12,13),(10,26),(26,10),(13,8),(8,13),(26,12),(12,26)\Big\}
$$
%\input{cp3M-1.pic}
}

\problempart Let $R$ be the map for all of MIT. What does the relation
$R^2$ represent in terms of connectivity between numbered buildings?
Can you generalize this?

\solution{
$R^2$ is the set of all pairs of buildings that are connected
via exactly 1 building. Similarly $R^3$ is the set of all
pairs of buildings that are connected via exactly 2
buildings. This notion can be generalized to $R^n$, where $(a,b)$ is in
$R^n$ iff $a$ and $b$ are connected via exactly $n-1$
buildings. We can recursively define $R^n$ as $R \circ R^{n-1}$.
Induction would thus be a natural way to go about proving this. It is
worth looking at the proof, which can be found both in the notes and in
Rosen.

It is important to notice that \emph{in general} it is not necessarily
true that $R^n$ must include $R^{n-1}, R^{n-2}, \ldots, R$ as well. In
our example, this was the case because the graph included self-loops and
bidirectional edges (symmetric relation), so one can meet the requirement
of going from building $a$ to building $b$ through $n-1$ intermedite
buildings by going around building $a$ as many times as necessary and
then proceeding to building $b$ (there are many similar time-wasting
ways to meet the requirement).
}

\problempart One of the important questions for course 6 students was,
is it possible to get from building 36 to building 10 without crossing
more than 5 other buildings? Write a proposition in terms of $R$,
using relational and set operators, which is true if this condition is
satisfied and false otherwise.

\solution{The key to solving this is to first write an expression for
the set of all buildings that are connected via 5 or fewer
buildings. In general, this would be $(R \union R^2 \union R^3 \union
\ldots \union R^6)$.  As explained above, in our case this is the same
as $R^6$. Then the predicate on $R$ is $(36,10) \in R^6$.  }

\problempart The MIT students would like to be able to get from any
building to any other building, without having to go outside. Write
the condition on $R$ that must be satisfied in order for this to be
true.

\solution{Let $\card{C}$ be $n$. In other words there are $n$
different buildings. The furthest apart two buildings can be, and
still be connected, is to be connected via $n-2$ other buildings
(prove this to yourself). Therefore the set $(R \union R^1 \union R^2
\union \ldots \union R^{n-1})$ represents all the pairs of buildings
that can reach one another without going outside. Because of the
self-loops, this is just $R^{n-1}$ since this set includes everything
else as well.

However we want every pair of buildings to be connected. The set of
all pairs of buildings is $C\times C$. Therefore the condition we want
to satisfy is $ C \times C\subseteq R^{n-1}$ (``the set of all
possible pairs of buildings is a subset of the set of buildings that
you can reach through $n-2$ intermediate buildings'').  }

\problempart MIT administration, however, wants to keep the number of
connections between buildings as small as possible. In other words, MIT
wants the size, $\card{R}$, of $R$ to be as small as possible. What is
the smallest $R$ that satisfies the requirement in part (d)?  Is the
smallest $R$ unique?

\solution{The smallest graph such that all the buildings are connected
would be to connect them in a straight line. The number of edges in
that graph is $n-1$. How do we know that this is the smallest number
of edges? Next week we will learn a theorem that says that the
smallest connected graph with vertices $n$ has at least $n-1$
edges. Each edge contributes two pairs therefore $\card{R} = 2(n-1)$.

The smallest graph is not unique, for starters we can connect the
buildings in a different order in the line. But there are many other
connected graphs with $n$ vertices and $n-1$ edges (any tree with $n$
nodes in fact satisfies this constraint, as we shall see next week).}

\end{problemparts}
\end{problem} 

\iffalse
% F01 PS3
% source: Velleman \S 4.5 exercise 13
% Used first time, revised by ARM 9/11/01

\begin{problem}
The Bassethound Bus Company is trying to decide on \emph{one-way} bus
routes to run among the cities
\begin{quotation}\noindent
San Francisco, Chicago, Dallas, New York, and Washington D.C.
\end{quotation}
Bassethound wants to make sure that there is always some way to follow its
routes and get from any of the cities to any other.  We will represent
Bassethound's routes by a binary relation, $B$, on the set, $C$, of cities
above.

\bparts
\ppart Succinctly express the property that Bassethound wants $B$ to have
using relational and set operators on $B$ and $C$.

\solution{From every city $c \in C$ there should be a possible
series of bus routes to get to any other city $c' \in C$. This implies that
$\forall (c, c') \in C \cross C, (c,c') \in B^*$ (transitive closure
of B). In other words, $C \cross C \subseteq B^*$.

Note that, since we know that $B^* \subseteq C \cross C$, it
equivalent to require that $C \cross C = B^*$.}

\eparts

However, Bassethound wants to run as few bus routes as possible.  That is,
Bassethound wants the size, $\card{B}$, of $B$ to be as small as possible.

\bparts
\problempart What is the smallest possible value of $\card{B}$?
Explain.

\solution{5. We can connect the cities in a ring with one way edges
between them. So for example, $B$ could be the set $\set{(SF,C) ,
(C,D) , (D,NY), (NY,W) , (W, SF)}$.

5 is the minimum number of edges possible because for each city to be
accessible there must be at least one edge entering the city. Hence
$B$ cannot have fewer than 5 edges.
}

\problempart
Is the smallest satisfactory $B$ unique?

\solution{No, since we could connect the cities in different orders.}

\ppart Unfortunately, Bassethound has a legacy problem.  They already have
a set of routes, $A$, that connect all the cities.  While they can cancel
routes easily, new routes are expensive, and they are reluctant to add
them.  Starting from $A$, can Bassethound arrive at a smallest size $B$
solely by cancelling routes?  Give a counterexample showing that it can't,
or explain how it can.

\solution{If $A$ has round trip direct from NY to each other city
(not unusual for these companies to have hubs), no route can be
cancelled and still maintain connectivity. But $A$ has 8 routes, not
the minimum number of 5. In general if a ring does not already exist
in the original $A$ digraph, there is no way to arrive at one.}

\eparts
\end{problem}


\begin{problem}
Let $A$ be the set of binary strings with length $k$.  For any two strings
$x, y\in A$, the \emph{Hamming distance}, $H(x,y)$, between $x$ and $y$ is
the number of bit positions where $x$ and $y$ are different.  For example,
\[
H(0000,0100)= 1, \qquad H(0110,1101)= 3.
\]
Let $R$ be the ``Hamming distance $\le 1$'' relation.  That is,
\[
x\, R\, y \quad\text{ iff }\quad  H(x,y) \le 1.
\]
Explain why the graph of $R^*$ is $A \cross A$.

\solution{We prove this by induction on the Hamming distance, $n$, between
binary strings.

Define
\[
P(n) \eqdef \quad \forall x,y\in A\ [H(x,y) = n] \implies xR^*y.
\]

{\em Base case} $n=0$: Suppose $H(x,y)=0$.  Then $x=y$.  Since $R^*$ is by
definition reflexive, we have $xR^*x$ and hence $xR^*y$.  This proves
$P(0)$.

{\em Inductive step}: Suppose $P(n)$ is true for some $n\ge 0$.  Consider
a pair of strings $x, y$ with $H(x,y) = n+1$.  Let $i$ be the leftmost bit
position where $x$ and $y$ differ (by the Least Number Principle).  Let
$z$ be a string which is identical to $x$ except in the $i^{th}$ bit.  So
$H(x,z) = 1$.  Therefore, $(x,z)\in R$, and so $(x,z)\in R^*$ by
definition of $R^*$.

Also, $z$ and $y$ are different exactly at the bit positions where $x$ and
$y$ are different, except for the $i^{th}$ bit, where the bits of $z$ and
$y$ are the same.  Therefore, $H(z,y) =n$.  By the induction hypothesis,
$(z,y)\in R^*$.  So $(x,z),(z,y) \in R^*$, and since $R^*$ is transitive,
$(x,y)\in R^*$ as well.  This proves $P(n+1)$.

Therefore by induction, $P(n)$ is true for all $n$.  It follows that any
pair $(x,y)\in A\times A$ is in $R^*$.  In other words, $A\times
A\subseteq R^*$.  Finally, since $R^*\subseteq A\times A$ by definition of
$R^*$, we conclude $R^* = A \times A$.}
 
%\end{problemparts}

\end{problem}
\fi

\instatements{\newpage}
\section*{Appendix}

\begin{definition*}

Let $R$ be a relation from a set, $A$, to a set, $B$, and $S$ be a
relation from $B$ to $C$.

The \emph{composition} of $S$ and $R$ is the relation from $A$ to $C$ with
\[
\graph{S \composition R} \eqdef \set{(a,c) \suchthat \exists b\ aRb \land bSc}.
\]
(Note the reversed order of $R$ and $S$ in the righthand side of this formula!)

The \emph{inverse}, $R^{-1}$, of $R$ is the relation from $B$ to $A$ with
\[
\graph{R^{-1}} \eqdef \set{(b,a) \suchthat aRb}.
\]

For $R$ a relation on a set, $A$, (that is, $R$ is from $A$ to $A$)
\[
R^* \eqdef \lgunion_{k=0}^\infty R^k.
\]
$R^*$ is the \emph{path relation} or \emph{reflexive
transitive closure} of $R$.

\[
R^+ \eqdef \lgunion_{k=1}^\infty R^k.
\]
$R^+$ is the \emph{positive length path relation} or \emph{transitive
closure} of $R$.

\end{definition*}

\end{document}

