\documentclass[11pt, twoside]{article}
\usepackage{epsf}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\askaboutsolutions

\begin{document}
\psol{4}{September 26, 2000}{2:35pm in lecture, October 3, 2000}


\textbf{Be sure to indicate your TA's name clearly on the solutions
your turn in}.

-----------------------------------------------------------------------------\\

\textbf{Self-study:  Matrices}
Read: Rosen \S 2.6 \\
Self-study problems (not to be handed in): 
Rosen \S 2.6, Exercises 1, 3, 5, 9, 13, 15, 23, 29, 31 \\

%[[[Miniquiz for tut4:  Use Exercise 29]]]

-----------------------------------------------------------------------------\\

\textbf{Reading:}
Rosen 7.1-7.5, 7.8, 8.1, 8.2, 8.4, 8.5 \\
% [[[This might be too much in Chapter 8---we can prune some of this
% out after I finish planning lecture 7.  We will probably not do much
% on tree-based algorithms.]]] DONE

\paragraph{New policy on collaboration}
Starting from today: If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.
 
\medskip
\begin{problems}

\problem
% Task scheduling or Dilworth
At last count, our 6.042 class contains 180 students.
Prove that the class must contain either:
(a) A set $S$ of 15 students such that, if they line up in size
places, they are also arranged in increasing order of age,
or
(b) a set $T$ of 13 students such that, if they line up in size
places, they are also arranged in decreasing order of age.




\solution{
\medskip
\textbf{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 180 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}=(180, 20)$, $P_{2} = (180, 21)$, $P_{3}= (185, 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 180 elements, it must either have a chain of size$>14$ or an antichain of size $\geq \frac{180}{14}$. 
\subparagraph{Case 1} $U$ has a chain of size $> 14$. Then it has a chain of size at least 15. This means that we can find 15 pairs which satisfy the relation $P_{1}\preceq P_{2}\preceq P_{3}\ldots \preceq P_{15}$. From the definition of our binary relation $(\preceq)$, this implies that $s_{1}\leq s_{2}\leq s_{3}\leq \ldots \leq s_{15}$ AND $a_{1} \leq a_{2} \leq a_{3}\leq\ldots\leq a_{15}$. Therefore, if we place the corresponding 15 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{180}{14}$, so, since antichains only come in integer lengths, it has an antichain of size at least 13. Therefore, we can find 13 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_{13}$ 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_{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}$).



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


  }

%[[[The idea here is supposed to be similar to the increasing sequence
%or decreasing sequence example that is suppressed in the lecture
%notes, under Dilworth's theorem material.  Order the students in the
%entire class by height.  Then use the argument about increasing or
%decreasing sequence.]]]

\problem
% digraphs, path counting and matrices
%Rosen 7.4, problem 11 but change the graph in Exercise 2 at least a
%little (because problem 11 has a solution in the back of Rosen).
%Type in the new problem.
%Also, we don't need 6 parts---maybe just three, the number of paths of
%length 3, 5, and 7

Find the number of paths of length 5 from a to e of in the directed graph shown below
\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\arabic{enumii})}
%% \begin{enumerate}
%% \item of length 2
%% \item of length 3
%% \item of length 5
%% \end{enumerate}

\begin{center}
\epsfxsize=4in
\epsfbox{figures/ps4p2.eps}
\end{center}



\solution{
\medskip
\textbf{Solution:}\\

%% \begin{enumerate}

%% \item 
%% \begin{enumerate}
%% \item a-b  b-a
%% \end{enumerate}

%% \item 
%% \begin{enumerate}
%% \item a-e e-a a-e
%% \item a-b b-c c-e
%% \item a-d d-b b-e
%% \end{enumerate}

%% \item
\begin{enumerate}
\item a-b b-e e-a a-b b-e
\item a-b b-c c-e e-a a-e
\item a-e e-a a-e e-a a-e
\item a-e e-a a-b b-c c-e
\item a-e e-a a-d d-b b-e
\item a-d d-b b-e e-a a-c
%% \item a-b b-c c-d d-b b-e
\end{enumerate}

%% \end{enumerate}

}  
%% end solution

\problem
% Digraphs
An {\em Euler path\/} in a digraph $G$ is a path that traverses all the
edges of $G$, each edge exactly once.  Unlike an Euler circuit, it
need not end up at the same vertex where it started.

Say whether each of the following digraphs has an Euler path, an
Euler circuit, both, or neither.
Justify your answers by exhibiting the circuits and paths that you say
exist, and proving that the others don't exist.


%[[[Put the actual graphs here, without giving them the citation from
%Rosen.]]]

%\bparts

%\ppart
\begin{enumerate}
\item
\epsfxsize=2in
\epsfbox{figures/ps4p3fig1.eps}
%\caption{Digraph a}
%[[[Digraph from Rosen section 7.5 ex. 24]]]

%\ppart
%% \item
%% \epsfxsize=2in
%% \epsfbox{figures/ps4p3fig2.eps}
% \caption{Digraph b}
% [[[Digraph from Rosen section 7.5 ex. 26]]]

%\ppart
\item
\epsfxsize=2in
\epsfbox{figures/ps4p3fig3.eps}
%\caption{Digraph c}

%[[[Digraph from Rosen section 7.5 ex. 28]]]
%\eparts
\end{enumerate}


\solution{
\medskip
\textbf{Solution:}\\

\begin{enumerate}

 
\item 
\begin{description}
\item[Euler Circuit] NO, because vertex $a$ has in-degree 1 and out-degree 2
\item[Euler Path] YES. Since it doesn't have an Euler Circuit and exactly 2 vertices have odd degree (i.e. $a$, $d$). E.g: $a,b,d,b,c,d,c,a,d$
\end{description}

%% \item
%% \begin{description}
%% \item[Euler Circuit] YES. One is: $a,d,b,d,e,b,e,c,b,a$
%% \item[Euler Path] YES. Since it has an Euler Circuit, it has an Euler path. The example above works here too.
%% \end{description}

\item
\begin{description}
\item[Euler Circuit] YES. E.g.: $a,b,c,e, b,d,c,b,f,d,e,f,e,a,f,a$
\item[Euler Path] YES. If a graph has an Euler Circuit, then it also
has an Euler path.  
\end{description} 

\end{enumerate}

  }

\problem
% graph coloring
For each of the following graphs, 
\begin{itemize}
\item Find the chromatic number
\item Say whether it is possible to decrease the chromatic number by removing a single vertex and all edges incident with it.
\end{itemize}

Justify your answers.
\bparts
\ppart
The graph in Rosen Section 7.8, exercise 4.
%% \ppart
%% The graph in Rosen Section 7.8, exercise 6.
\ppart
The graph in Rosen Section 7.8, exercise 8.
\eparts
%[[[George:  You might want to reduce this, e.g., to 2 parts instead
%of 3.]]]


\solution{
\medskip
\textbf{Solution:}\\
\begin{enumerate}
\item Since there is a triangle, at least 3 colors are needed. To show that 3 colors suffice, notice that we can color the vertices around the outside alternately using red and blue, and color vertex $g$ green.

If we remove vertex $g$, the chromatic number will be reduced to 2. We can color vertices $f,b,d$ blue and $a,c$ and $e$ red

%% \item Since there is a triangle, at least 3 colors are needed. The coloring in which $b$ and $c$ are blue, $a$ and $f$ are red, and $d$ and $e$ are green shows that 3 colors suffice. 

Even if we remove a vertex, at least one of the two triangles $ace$ and $bdf$ must remain since they share no vertices. Therefore, the smaller graph will still have chromatic number 3. 

\item Since vertices $b,c,h,i$ form a $K_{4}$, at least 4 colors are needed. A coloring using only 4 colors is indeed possible: eg: let $a$ and $c$ be red, $b,d$ and $f$ blue,: $g$ and $i$ green and $e$ and $h$ yellow.

If we remove vertex $h$ and recolor vertex $e$ red, then we can eliminate color yellow from the solution, thus reducing the chromatic number to 3. 

\end{enumerate}
  }



\problem

Rosen section 7.5, exercise 44.


\solution{
\medskip
\textbf{Solution:}\\

This graph has no Hamiltonian circuit. If it did, then certainly the circuit would have to contain edges ${d, a}$ and ${a,b}$, since these are the only edges incident to vertex $a$. By the same reasoning, the circuit would have to contain the other six edges around the outside of the figure. These eight edges already complete a circuit, and this circuit omits the nine vertices on the inside. Therefore there is no Hamiltonian circuit.


  }

\problem
% trees
%Rosen section 8.1, exercise 18
Either describe what a full $m$-ary tree with $76$ leaves and height $3$, where
$m$ is a positive integer, would look like, or show that no such tree exists.


\solution{
\medskip
\textbf{Solution:}\\
 

Such a tree does exist. We first note that such a tree  must have $i=\frac{75}{m-1}$ internal vertices. This has to be a whole number, so $m-1$ must divide $75$. This is possible, for example when $m=6$. Let's try to construct such a tree: A complete $6$-ary tree of height $2$ would have $36$ leaves. We therefore need to add $40$ leaves. This can be accomplished by changing $8$ vertices at level $2$ to internal vertices; each such change adds 5 leaves to the tree ($6$ new leaves at level $3$, minus the one leaf at level 2 that has been changed to an internal vertex). So the tree looks like this:
The root has $6$ children, each of which has $6$ children, giving $36$ vertices at level $2$. Of these, $28$ are leaves and each of the remaining $8$ vertices at level $2$ has $6$ children living at level 3, for a total of $48$ leaves at level $3.$ The total number of leaves is thus $48+28=76$, as desired.

  }

\problem 
% trees
 
Rosen 8.2 exercise 8.  How many weighings of a balanced scale are
needed in order to find a counterfeit coin among eight coins if the
the counterfeit coin is either heavier or lighter than the others?
Describe an algorithm to find the counterfeit coin using this number
of weighings.  

\solution{
\medskip
\textbf{Solution:}\\
 
Decision tree theory applied naively says that at least $log_{3}8=2$ weighings are needed, but in fact at least 3 weighings are needed. To see this, consider what the first weighing might accomplish. We can put one, two or three coins in each pan. If we put one in each pan, and the scale balances, what we know is that the counterfeit must be among the remaining 6. Similarly, if we put 2 and the scale balances, we narrow down our list of suspects to the remaining 4. If we put 3 in each pan and the scale balances, we are in really good shape, but what if it doesn't? Then our list of suspects will be the 6 coins in the scale. What this means is that however many coins we choose to put on each pan (1,2 or 3), there's always a case where the list of suspects after the first weighing will be $\geq 4$. One weighing is not enough to distinguish the counterfeit from among a list of 4 suspects.


 In Tutorial 1, we showed that we can solve a bigger problem (12 coins) with three weighings, so we should be able to solve this one with the same number of weighings. So if we are lazy and we want to just use the algorithm we came up with in Tutorial, we just add 4 good coins to our collection and apply that algorithm. 

However, a simpler solution is available: Put two coins in each pan. If the scale balances, then the search is reduced to the other four coins. If the scale does not balance, then the counterfeit is among the four coins on the scale. In both cases, after 1 weighing we have cut down our list of suspects to 4. Call them A, B, C, D. First compare coins A and B. If they balance, then the counterfeit must be among the other 2. In this case, compare C with A (which we now know must be good). If they balance, then D is counterfeit. If not, C is counterfeit. On the other hand, if A and B do not balance, then one of them is the counterfeit. Compare A with C (which we know must be good). If they balance, B is the counterfeit. If they do not, A is the counterfeit.  


  }


\end{problems}
\end{document}

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

tutorial4:

1. Course scheduling:
Leftover problem from tut3

\problem \textbf{Scheduling Courses}
% source: fall98/tutorials/H19-rec4.tex, beginning

We consider a simple kind of scheduling problem --- for MIT courses with
prerequisites.  The problem is to determine how a student could complete
all of the courses in the fewest terms, under the simplifying, if
unlikely, assumption that there is no limit on the number of courses a
student can take in a term as long as their prerequisites have all been
met.  We model this problem with a digraph.  An example is shown in
Figure~\ref{fig:dag}.

\begin{figure}[htbp!]
	%graphic is from  /a/class/6.042/spring00/archive/lectures/
 \centerline{\resizebox{!}{2.0in}{\includegraphics{../handouts/figures/dag}}}

  \caption{This is a picture of a directed acyclic graph.  Vertices
    are labeled with course numbers.  An edge from $u$ to $v$
    indicates that course $u$ is a prerequisite for course $v$.}

  \label{fig:dag}
\end{figure}

\problempart What's the length of a critical path; find such a path.
\problempart  How many terms are necessary and sufficient to complete all of the
courses in Figure~\ref{fig:dag}, assuming prerequisites are observed,
but course load is no issue? Prove your answer (both necessary and sufficient).

\solution{
\medskip
\textbf{Solution:}\\
The answer is suggested by the way Figure~\ref{fig:dag} is drawn.
Each term the student could take all the courses in a horizontal row,
starting with the first row and working down.  All of the courses in
each row are incomparable, and all the necessary prerequisites are in
previous rows.  Since there are six rows, the student can finish in
six terms.

Furthermore, there is no way to finish in fewer than six terms, since each
term the student can take at most one course in the six-course sequence
18.01, 18.03, 6.002, 6.004, 6.033, 6.857.  Notice that this sequence
constitutes the longest directed path in the graph.
}

%\problempart Show that there is a schedule for taking courses
%which achieves the minimum number of terms, $t$.  
%the previous question includes this direction

\solution{
\medskip
\textbf{Solution:}\\
    The solution to the previous part implies that $t$ terms are
    sufficient.  In term $i$, the student should take the set of
    courses in the $i$th block.  Since the edges into any block come
    from an earlier block, all the prerequisites of courses in a block
    have been taken by the time the block is scheduled to be taken.
    And since the blocks partition the set of all courses, the student
    will complete every course.
  }

2. % Digraphs
Show that every tournament graph has a Hamiltonian path.
[[[This should be a quick exercise, basically deciphering definitions
and reviewing a previous proof done in tutorial, about tournaments.
I think it's the same question as constructing a ``nice'' ordering.]]]

3. % Undirected graphs, wrong proof
Problem 1 from Spring 2000 tutorial 4 (about line graphs)
[[[As an alternative, there's a cute set of proofs about ``tangled''
and ``mangled'' graphs.  I think this was used last spring also, but
in a pset instead of tutorial.  Take a look and see which you like better.]]]


4. [[[Something about trees?]]]

5. 
The diagram depicts a weighted graph G, with integer weights on the edges as shown. 
Try to find a spanning tree of G with the smallest possible total edge weight (that is, a Minimum Spanning Tree). 


\solution{
\medskip
\textbf{Solution:}\\
 Note to the TA's: don't try to teach the general theory. Run a ``competition''. The students should devise various procedures for constructing a tree. Try to explain why this procedure gives the smallest possible tree. 

  }




