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

%\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{3F}                    % !! start the paper

\begin{theorem}[Dilworth]
  For all $t$, every poset with $n$ elements must have either a chain
  of size greater than $t$ or an antichain of size at least $n / t$.
\end{theorem}


% source: Fall00 Problem Set 3
% Velleman \S 4.4, Exercise 1.

\begin{problem}

In each case, say whether or not $R$ is a partial order on $A$.  If
so, is it a total order?

\begin{problemparts}

\problempart $A=\{a,b,c\}, R=\{(a,a),(b,a),(b,b),(b,c),(c,c)\}.$

\problempart $A=$\{the set of all words in English\} 

$R = \{(x,y) \in A \times A$ and the word $x$ comes before the word $y$
alphabetically\}.


\problempart $A=\reals, R=\{(x,y) \in \reals \times \reals \mbox{ and
} |x| < |y|$ or $x=y\}$.

\problempart $A=\reals, R=\{(x,y) \in \reals \times \reals \mbox{ and }
|x|\leq |y|\}$.

\end{problemparts}

\solution{
a. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$ is
a partial order on $A$.  However, it is not a total order on $A$ since
neither the pair $(a,c)$ nor $(c,a)$ is in $R$.\\


b. $R$ is not reflexive (although it is transitive and antisymmetric),
and thus it is not a partial order on $A$.\\


c. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$ is
a partial order on $A$. However, $R$ is not a total order on $A$. As a
counterexample, if x = 5, y = -5, then none of the following holds: $x
= y, |x| < |y|, |y| < |x|$.

d. $R$ is reflexive and transitive. However, it is not
antisymmetric. As a counterexample, $|-3| \leq |3|, |3| \leq |-3|$,
but $3 \neq -3$.  
}

\end{problem}

%-----------------------------------------------------------------%
% source: karger tutorial spring 01
% used previous as pset, but was too hard apparently (see comment)
% topic: Dilworths theorem

% old comment:
% this problem appeared in a problem set in fall 00
% very few people who didn't go to office hours got it right, even though
% it's not particularly difficult. 
% Perhaps doing it in tutorial is a better idea

\begin{problem}
At last count, our 6.042 session contained approximately 60 students.
Prove that the class must contain either: 

\begin{enumerate} 
\item A set $S$ of 7 students such that, if they line up according to
increasing height, they are also arranged in increasing order of age,
or

\item a set $T$ of 7 students such that, if they line up according to
increasing height, they are also arranged in decreasing order of age.
\end{enumerate}

To eliminate some confusion: the sequence $\{2, 2, 3, 4\}$ is in
increasing order, but not in strictly increasing order.

\solution{
For each student, we can assign a pair $(s,a)$ where $s$ represents
the size (height) of the student and $a$ represents the age of the
student. We then get a set $U$ of 60 such pairs. We can define the
following binary relation $R$, denoted by $\preceq$, between two pairs
$P_{1}$ and $P_{2}$: $P_{1}\preceq P_{2}$ iff $s_{1}\leq s_{2}$ and
$a_{1}\leq a_{2}$.

For example, if $P_{1}=(60, 20)$, $P_{2} = (60, 21)$, $P_{3}= (65,
19)$, we have $P_{1}\preceq P_{2}$ but $P_{3}$ and $P_{1}$ are
incomparable.

It is easy to check that $R$ is reflexive, transitive and
antisymmetric. Thus, it defines a partial order on the set $U$. By
Dilworth's Theorem, since $U$ has 60 elements, it must either have a
chain of size$>7$ or an antichain of size $\geq \frac{60}{7}$.

\subparagraph{Case 1}
$U$ has a chain of size $> 7$. Then it has a chain of size at least
7. This means that we can find 7 pairs which satisfy the relation
$P_{1}\preceq P_{2}\preceq P_{3}\ldots \preceq P_{7}$. From the
definition of our binary relation $(\preceq)$, this implies that
$s_{1}\leq s_{2}\leq s_{3}\leq \ldots \leq s_{7}$ AND $a_{1} \leq
a_{2} \leq a_{3}\leq\ldots\leq a_{7}$. Therefore, if we place the
corresponding 7 students in the same order, they will be lined up in
in increasing order of size AND in increasing order of age.

\subparagraph{Case 2} 
$U$ has an antichain of size $\geq\frac{60}{7}$, so, since
antichains only come in integer lengths, it has an antichain of size
at least 8. Therefore, we can find 8 pairs which are
incomparable. We can line them up in order of increasing size
(ignoring age), and come up with an order $P_{1}\ldots P_{8}$ so that
$s_{i} \leq s_{i+1} (i= 1\ldots 12)$. Since for all $i$, $s_{i}\leq
s_{i+1}$ and $P_{i}, P_{i+1}$ are incomparable, we can conclude that
$a_{i}> a_{i+1}$ (because if not, $a_{i}\leq a_{i+1}$ so for that $i$,
$s_{i}\leq s_{i+1},$ $a_{i}\leq a_{i+1}$, therefore $P_{i}\preceq
P_{i+1}$, so $P_{i}$ and $P_{i+1}$ would NOT be incomparable.) If we
take the students corresponding to $P_{1}\ldots P_{8}$ and line them
up in that order, they will be in increasing order of size (since
$s_{i}\leq s_{i+1}$) and in decreasing order of age (since we
established that $a_{i}>a_{i+1}$).

} % end solution
\end{problem} 

%-------------------------------------------------------------
% source: spring00 ps3 
% topics: critical path, DAGs, topological sort

\begin{problem} A pair of 6.042 TAs, Carole and George,
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 George' copy of the notes for tutorial 3.

\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 Carole'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}

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

\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]
    \begin{center}
    \unitlength=0.047pt
    \input{figures/ps4-1.latex}
    \end{center}
    \caption{Graph representing the task precedence constraints.}
    \label{fig:tasks}
    \end{figure}
}

\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 Carole and George 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,
Carole 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 Carole and George want to know how long conquering the
galaxy will take.  George 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
Carole and George from both working all the time.}

\problempart Carole proposes a different method for determining the
duration of their project.  She 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, Carole and George may be unable to make progress
on the critical path every day.}

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

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

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

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

\end{document}
