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

% source Vellemen 4.4.6
% not used before

\begin{problem} Let $B$ be a set of numbers and let $R$ be
the divisibility relation on the set $B$.  In other words, $aRb$ iff $a
\divides b$, that is, iff $ak=b$ for some natural number $k$.

\begin{problemparts}
\problempart Let $B = \{2,3,4,5,6,7,8\}$.  Draw a \emph{Directed Acyclic
Graph} (DAG) for the poset $(B,R)$.  What are the minimal and maximal
elements? \footnote{An element $a$ is {\bf maximal} in the poset $(S,
\preceq)$ if there is no $b \in S$ such that $a \prec b$. Similarly, $a$
is {\bf minimal} if there is no element $b \in S$ such that $b \prec a$.}

\solution{
The minimal elements are 2, 3, 5, 7. The maximal elements are 5, 6, 7, 8.

    \begin{figure}[htbp]
    \begin{center}
    \includegraphics{figures/dag1.jpg}
    \caption{DAG for poset $(B,R)$}
    \end{center}
    \end{figure}
}

\problempart Let $B$ be the set, $\naturals^{+}$, of integers greater than
1.  What are the minimal and maximal elements?

\solution{All prime numbers are minimal elements of the poset $(B,R)$
since no numbers divide them.  Prime numbers divide all other numbers in
their chains and can thus be considered the ``head'' of the chain.

There is no maximal element.  For any $n$, we can create a larger number,
namely $2n$, so the poset $(B,R)$ does not have a maximal element.  Note
that a maximal element here is a number which is divisible by all the
numbers in the chain (and can thus be considered as the ``tail'' of the
chain).  Since we can always make a larger number in the chain, no such
maximal element exists.}

\problempart Let $B$ be the set, $\naturals$, of all natural numbers
(including zero).  What are the maximal and minimal elements?

\solution{The minimal element is 1 since 1 divides all natural
numbers. The maximal element is 0 since all numbers divide 0.}

\end{problemparts}
\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

% revised to give them the partial order, and then let them use
% dilworth to prove the claim. (Rad)

\begin{problem}

For each student in our 6.042 class, we can assign a pair $(s,a)$ where
$s$ represents the size (height) of the student and $a$ represents the age
of the student. Consider the relation, $R$, between pairs defined by the
following condition:
\[
(s_1,a_1)\, R\, (s_2,a_2) \quad\text{iff}\quad s_{1}\leq s_{2} \land a_{1}\leq
a_{2}.
\]

At last count, our 6.042 class contained approximately 150 students.
Prove that the class must contain either:

\begin{enumerate} 
\item A set $S$ of 13 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 13 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: in these problems, when we say ``increasing''
we mean \emph{weakly} increasing.  A \emph{weakly increasing} sequence may
stay the same at some steps, it just never gets smaller; a \emph{strictly
increasing} sequence gets bigger at \emph{every} step.  For example, the
sequence $\{2, 2, 3, 4\}$ is in \emph{weakly} increasing order, but not in
\emph{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 150 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 150 elements, it must either have a
chain of size$>12$ or an antichain of size $\geq 150/12$, that is, an
antichain of size $\geq 25/2$.

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

\subparagraph{Case 2} 
$U$ has an antichain of size $\geq 25/2$, so, since antichains only come
in integer lengths, it has an antichain of size at least 13.  Therefore,
we can find 13 pairs $P_1,\dots, P_{13}$, 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_{13}$ so that $s_{i} \leq s_{i+1} (i= 1\ldots
13)$.  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
\emph{not} be incomparable.)  If we take the students corresponding to
$P_{1}\ldots P_{13}$ 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

\hint Use:

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

\end{problem} 

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

\begin{problem} A pair of 6.042 TAs, Adrian and Min,
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 Min'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 Adrian'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 Adrian and Min 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,
Adrian 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 Adrian and Min want to know how long conquering the
galaxy will take. Min 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
Adrian and Min from both working all the time.}

\problempart Adrian 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, Adrian and Min may be unable to make progress
on the critical path every day.}

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

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

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

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

\end{document}
