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

\newcommand{\ra}{\rightarrow}

\begin{document} 
\inclassproblems{3, Tue.}                    % !! start the paper


\begin{problem} A pair of 6.042 TAs, Grant and Sonya,
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 Sonya's copy of the lecture notes.

\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 Grant's cat, Emilios - 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}

We picture this information in Figure 1 below by drawing a point for each
task, and labelling it with the name and weight of the task.  An edge
between two points indicates that the task for the higher point must be
completed before beginning the task for the lower one.
    \begin{figure}[htbp]
    \begin{center}
    \unitlength=0.047pt
    \input{figures/ps4-1.latex}
    \end{center}
    \caption{Graph representing the task precedence constraints.}
    \label{fig:tasks}
    \end{figure}

\begin{problemparts}

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

\solution{
We can easily find several of them. The most natural one is valid, too:
\#1, \#2, \#3, \#4, \#5, \#6, \#7, \#8.
}

\bigskip

\noindent Grant and Sonya 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,
Grant cannot work on building a fleet for a few days, run get shots
for Emilios, 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.

\problempart Grant and Sonya want to know how long conquering the
galaxy will take.  Sonya 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?

\solution{
\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
Grant and Sonya from both working all the time.}

\problempart Grant proposes a different method for determining the
duration of their project.  He suggests looking at the duration of
the ``critical path'', the most time-consuming 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?

\solution{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, Grant and Sonya may be unable to make progress
on the critical path every day.}

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

\solution{
40 days.  Tasks could be divided as follows:

Sonya: \#1 (days 1-8), \#3 (days 9-17), \#4 (days 18-28), \#8 (days
33-40).

Grant: \#2 (days 1-18), \#5 (days 19-28), \#6 (days 29-32), \#7 (days
33-38).  
}
\end{problemparts}
\end{problem} 


\begin{problem}
Verify that each of the following relations is a partial order.  For each,
indicate if it is strict, weak, and/or a total order.  (Definitions are in
the Appendix.)

\bparts

\ppart The superset relation, $\supseteq$, on some family of sets.

\solution{To prove $\supseteq$ is transitive, suppose $A \supseteq B$ and
$B \supseteq C$.  Then by definition of $\supseteq$, every $b \in B$ is
also in $A$, and every $c \in C$ is also in $B$.  Hence, every $c \in C$
is also in $A$, which proves that $A \supseteq C$.  This proves that
$\supseteq$ is transitive.  It is also antisymmetric, because $A \supseteq
B$ and $B \supseteq A$ implies $A = B$.  Finally, it is reflexive, since
$A \supseteq A$.  So $\supseteq$ is a weak partial order.

There are lots of pairs of sets neither of which contains the other, so
$\supseteq$ will not, in general, be a total order.}

\ppart The ``divides'' relation on natural numbers.
\solution{Suppose $k \divides m$ and $m \divides n$.  So there are
integers, $k_1,k_2$ such that $m = k_1 k$ and $n = k_2 m$.  Hence, $n =
k_2(k_1 k) = (k_2k_1) k$, which means that $k \divides n$.  So ``divides''
is transitive.  Similarly, if $m \divides n$ and $n \divides m$, then
$m=n$, so divides is antisymmetric, and so is a partial order.  It is
weak, because every integer divides itself.  It is not total, since any
two primes, for example, are incomparable.
}
\eparts
\end{problem}

\begin{problem}
\bparts

\problempart What are the maxim\emph{al} and minim\emph{al} elements, if
any, of the set, $\naturals$, of all nonnegative integers under
divisibility?  Is there a minim\emph{um} or maxim\emph{um} element?

\solution{The minimum (and therefore unique minimal) element is 1 since 1
divides all natural numbers. The maximum (and therefore unique maximal)
element is 0 since all numbers divide 0.}

\problempart What are the minimal and maximal elements, if any, of the set
of integers $\ge 2$ under divisibility?

\solution{All prime numbers are minimal elements, since no numbers divide
them.

There is no maximal element, because for any $n\ge 2$, there is  a
``larger'' number under the divisibility partial order, namely,
$mn$, for any $m > 1$.}


\ppart
What is the size of the longest chain that is guaranteed to exist in any
partially ordered set of $n$ elements?  What about the largest antichain?

\solution{
Chain size is 1 in the ``discrete'' partial order in which every two
distinct elements are incomparable.  Antichain size is 1 if the partial
order is total.
}

\iffalse

\ppart Describe a partially ordered set that has no minimal or maximal
elements.

\solution{$\integers$, $\reals$, etc.}

\ppart Describe a partially ordered set that has a \emph{unique minimal}
element, but no minimum element. \hint It will have to be infinite.

\solution{
$\integers \union{i}$ where $i$ is a root of $-1$, under the usual order
$\integers$.  So $i$ is incomparable to everything but itself, and is
therefore minimal.
}
\fi

\eparts
\end{problem}


\begin{problem}
Prove that a binary relation, $R$, on a set, $A$, is a strict partial
order iff it is transitive and irreflexive.

\solution{
If $R$ is a strict p.o., then in particular, it is asymmetric.  So $aRa$
would imply $\neg(a R a)$, a contradiction.  It follows that $aRa$ cannot
hold, so $R$ is irreflexive.

Conversely, suppose $R$ is transitive and irreflexive.  We want to show
that $R$ is antisymmetric.  So suppose it wasn't.  Then there must be $a,b
\in A$ such that $aRb$ and $bRa$.  Now transitivity implies that $aRa$,
contradicting irreflexivity.  This contradiction shows that $R$ must be
antisymmetric.
}
\end{problem}

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

\subsection*{Relational Properties}
A binary relation, $R$, on a set, $A$, is
\begin{itemize}

\item \emph{transitive} if for every $a,b,c\in A$, $aR b$ and
    $bR c$ implies $aR c$.

\item \emph{asymmetric} if for every $a,b\in A$, $aR b$ implies 
    $\neg(bR a)$,

\item \emph{reflexive} if $a R a$ for every $a \in A$,

\item \emph{antisymmetric} if for every $a \neq b\in A$, $aR b$ implies 
    $\neg(bR a)$,

\item \emph{irreflexive} if $a R a$ holds for no $a \in A$.

\end{itemize}


\subsection*{Partial Order}

A binary relation is a \emph{strict partial order} iff it is transitive
and asymmetric.  It is a \emph{weak partial order} iff it is transitive,
reflexive, and antisymmetric.

Let $\preceq$ be a weak (reflexive) partial order on a set, $A$.
\begin{itemize}

\item An element $a \in A$ is \emph{minimal} iff there is no element in
$A$ that is $\preceq a$ except possibly $a$ itself.  Similarly, an element
$a \in A$ is \emph{maximal} iff there is no element in $A$ that is
$\succeq a$ except possibly $a$ itself.

\item An element $a \in A$ is a \emph{lower bound} for a subset, $S
\subseteq A$ iff $a \preceq s$ for every $s \in S$.  Similarly, an element
$a \in A$ is an \emph{upper bound} for a subset, $S \subseteq A$ iff $s
\preceq a$ for every $s \in S$.

\item An element $a \in A$ is the \emph{minimum} element iff $a$ is a
lower bound on $A$.  Similarly, an element $a \in A$ is the \emph{maximum}
element iff $a$ is an upper bound on $A$.

\item Elements $a,b \in A$ are \emph{comparable} iff either $a \preceq b$
or $b \preceq a$.  Two elements are \emph{incomparable} iff they are not
comparable.

\item A subset, $S \subseteq A$ is \emph{totally ordered} iff every
two distinct elements in $S$ are comparable.

\item A \emph{chain} is a totally ordered subset of $A$.  

\item An \emph{antichain} is a subset of $A$, such that no two elements in
it are comparable.

\iffalse
\item An element $a \in A$ is the \emph{greatest lower bound (glb)} of a
subset, $S \subseteq A$ iff $a$ is a lower bound for $S$, and if $b \in A$
is also a lower bound for $S$, then $b \preceq a$.  Similarly for
\emph{least upper bound (lub)}.
\fi

\end{itemize}

\end{document}



