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

\problem There are 70 healthy students, 60 wealthy students, and 50
wise students, 40 healthy and wealthy students, and 30 wealthy and
wise students.  What is the largest possible number of students that
could be healthy, wealthy, and wise?

\solution{
Let $H$ be the set of healthy students, let $\$$ be the set of wealthy
students, and let $W$ be the set of wise students.  By
inclusion-exclusion, we have:

\beqn
|H \cup \$ \cup W|
	& = &	|H| + |\$| + |W|
		- |H \cap \$| - |H \cap W| - |\$ \cap W|
		+ |H \cap \$ \cap W|
\eeqn

Plugging in the numbers provided above, we find:

\beqn
|H \cup \$ \cup W|
	& = &	70 + 60 + 50
		- 40 - |H \cap W| - 30
		+ |H \cap \$ \cap W| \\
|H \cup \$ \cup W|
	& = &	110 - |H \cap W| + |H \cap \$ \cap W| \\
|H \cap \$ \cap W|
	& = &	|H \cup \$ \cup W| + |H \cap W| - 110
\eeqn
}

















\problem A graph is {\em planar} if there is a way to draw it on a
piece of paper so that no edges cross.  For example, the graph on the
left is planar, but the graph on the right is not:

\bigskip
\centerline{\resizebox{!}{1in}{\includegraphics{pset6-planar.eps}}}
\bigskip

The graph on the left is planar, because it can be redrawn so that no
edges cross:

\bigskip
\centerline{\resizebox{!}{1in}{\includegraphics{pset6-planar2.eps}}}
\bigskip

If a graph is drawn so that no edges cross, then the edges divide the
plane into regions called {\em faces}.  For example, the graph above
has five faces, four bounded by edges and one surrounding the whole
figure.

Let $V$ be the number of vertices in a planar graph, let $E$ be the
number of edges, and let $F$ be the number of faces.  Use
well-ordering to prove that:

\beqn
V - E + F & = & 2
\eeqn

In the example above, there are $V = 6$ vertices, $E = 9$ edges, and
$F = 5$ faces, and $6 - 9 + 5 = 2$.

-------------------------------------------------------------------------------



\begin{problem}
Which of the following relations are equivalence relations?  For those
that are equivalence relations, what are the equivalence classes? For
those that are not, give an example of how they fail.

\begin{problemparts}
\problempart
$R \eqdef \set{(x,y) \in W \times W \suchthat \text{ the words $x$ and
$y$ start with the same letter} }$ where $W$ is the set of all words
in the 2001 edition of the Oxford English dictionary.

\solution{
$R$ is an equivalence relation since it is reflexive, symmetric, and
transitive.  The equivalence class of $x$ with respect to $R$ is the
set $[x]_R = $ the set of words $y$, such that $y$ has the same first
letter as $x$. There are 26 equivalence classes, one for each letter
of the English alphabet.
}

\problempart
$S \eqdef \set{(x,y) \in W \times W \suchthat \text{ the words $x$ and $y$
have at least one letter in common} }$.

\solution{
$S$ is reflexive and symmetric, but it is not transitive.  Therefore, $S$
is not an equivalence relation.  For example, let $w_1$ be the word
``scream,'' let $w_2$ be the word ``and,'' and let $w_3$ be the word
``shout.''  Then $w_3 S w_1$, and $w_1 S w_2$, but it is \textbf{not} the
case that $w_3 S w_2$.}

\problempart
$R \eqdef \set{(x,y) \in \reals \times \reals \suchthat x-y \in \rationals }$.

\solution{
$R$ is reflexive since, for any $x\in R$, $x-x=0$.  $R$ is symmetric
because if $(x-y)$ is rational, then $(y-x)=-(x-y)$ is rational as well.
Finally, $R$ is also transitive.  To see this, consider $(x,y)\in R$ and
$(y,z)\in R$.  We would like to know if $(x,z)$ is also in $R$.  We start
by noting that $(x-y)\in \rationals$ and $(y-z)\in \rationals$ by
definition of our relation $R$.  Now, we can express $(x-z) =
(x-y)+(y-z)$.  Since the sum of any two rational numbers is another
rational number, and we have written $(x-z)$ as such, we have shown that
$(x,z)\in \rationals$.  Therefore, $R$ is transitive.  Since $R$ is also
reflexive and symmetric, $R$ is an equivalence relations on $\reals$.

The equivalence class for x is
\[
[x]_R = \set{x + r \suchthat r \in \rationals}.
\]
}

\problempart
$R \eqdef \set{(x,y) \in \reals \times \reals \suchthat \exists n \in
\integers\; y=10^{n} x}$.

\solution{
$R$ is reflexive, since we can set $n=0$.  $R$ is symmetric because if
$y=10^k x$, for some $k\in \integers$, then $x=10^{-k}y$, so if
$(x,y)\in R$, then $(y,x)\in R$.  We can show that $R$ is transitive
as follows: consider pairs $(x,y)\in R$ and $(y,z)\in R$.  So $y=10^nx$
and $z=10^m y$, for $m,n\in \integers$.  Then, substituting, we have
that $z=10^{m}(10^{n} x) = 10^{m+n}x$.  Since $m+n \in \ints$, we conclude
that $(x,z) \in R$.

The equivalence class for x is 
\[
[x]_R = \set{10^{n}x \suchthat n\in \integers}.
\]
There is a distinct equivalence class for every real number in the
intervals $(-10,-1] \union \{0\} \union [1, 10)$.
}

\end{problemparts}

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

\solution{
\begin{enumerate}

\item $\exists x \exists y, \exists z \,(x \neq y \oand y \neq z
\oand x \neq z \oand \cult{x} \oand \cult{y} \oand \cult{z})$ %at
least 3 people are in the cult

\item $\forall x\,\, \neg \cult{x}\,\, \exists y,\,\, \exists z \,\,(x \neq y
\oand y \neq z \oand z \neq x \oand \neg
(\cult{y} \oor \cult{z}))$ %either everyone is in the cult or there are at
                               %least 3 people who are not in the cult

\item $\neg (\forall x, \fl{x} \Rightarrow \neg \cult{x})$ %at least
one member of the cult sits on the %first floor

\item $\exists x \,(\neg \fl{x}\,\, \oand \cult{x})$  %not everyone who sits
                                                        %on the second floor
                                                        %is in the cult.  This
                                                        %establishes that
                                                        %there are three
                                                        %people in the cult
                                                        %since at least one
                                                        %person is not in the
                                                        %cult.

\item $\cult{\mathtt{Cormen}} \Rightarrow \neg\cult{\mathtt{Aslam}}$.
%Either Cormen is in the cult and Aslam isn't or Aslam is in the cult and
%Cormen isn't 
                                                             
\item $\neg \fl{x} \oand \neg \recent{x} \Rightarrow \neg \cult{x}$.
%Nicol is not in the cult.

\item $\cult{\mathtt{Kotz}} \Rightarrow \cult{\mathtt{Nicol}}$
%  Kotz can't be in the cult either.

\item $\neg(\neg \cult{\mathtt{Drysdale}} \oor \cult{\mathtt{Aslam}})$
% Aslam cannot be in the cult....therefore Cormen is in the cult.

%since there must be three members of the cult, and Aslam, Nicola and Kotz are
%not in the cult, Hawblitzel is in the cult.
\end{enumerate}
}