\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\usepackage{graphics}
\input{../handouts/macros-course}


\newif\ifspaceout
\spaceouttrue
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{3in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
\newcommand{\nextproblem}{\ifspaceout\newpage\fi}


\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\askaboutsolutions

\begin{document}
%\querysol{q1}{Quiz 1}{March 14 2001}{q1sol}{Quiz 1 Solutions}{March 21 2001}

\ifshowsolutions
\qsol{1}{March 20 2001}
\spaceoutfalse
\else
\exam{Quiz 1}{March 14 2001}
\fi

%\titlebar

\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{c@{\hskip 3em}c@{\hskip 3em}c@{\hskip 3em}c}
George & Joe & Josh & Kavita \\
\ &&& \\
Ivan & Ray & Tina &
\end{tabular}
\end{center}

\medskip

\noindent Write the hour at which your Friday recitation begins \brule{3em}

\medskip

\begin{closeitemize}
\item This quiz is open book/notes.  

\item There are 10 pages with 8 problems totaling 90 points.  Problem 
  parts are labeled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{these
    pages may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

\item You may assume any of the results presented in class or in the
  lecture notes.

\item Show your work, as partial credit will be given.  You will be
  graded not only on the correctness of your answer, but also on the
  clarity with which you express it.  {\bf Be neat and write legibly}.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\medskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  10 & & \\ & & & \\\hline & & &\\
2 &  10 & & \\ & & & \\\hline & & &\\
3 &  10 & & \\ & & & \\\hline & & &\\
4 &  10 & & \\ & & & \\\hline & & &\\
5 &  10 & & \\ & & & \\\hline & & &\\
6 &  10 & & \\ & & & \\\hline & & &\\
7 &  15 & & \\ & & & \\\hline & & &\\
8 &  15 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 90 & & \\
& & &\\
\hline
\end{tabular}
\end{center}


\newpage

\begin{problems}

\problem\pts{10} \textbf{Quantifiers}

% Spring 2000 - Need to do something similar

Consider the following predicates where the universe of discourse is
the set of all living things:
\begin{description}
\item[$P(x)$:] $x$ is a monkey
\item[$Q(x)$:] $x$ is a 6.042 TA
\item[$R(x)$:] $x$ comes from the 23rd century
\item[$S(x)$:] $x$ likes to eat pizza
\end{description}
Express each of the following statements using quantifiers, logical
connectives, and and the above predicates:
\begin{problemparts}
\ppart  \onept No monkeys like to eat pizza.

\solution{\medskip
\textbf{Solution:}
$(\forall x) (P(x) \implies \neg S(x))$}

\smallspace
\ppart  \onept Nobody from the 23rd century dislikes eating pizza.

\solution{\medskip
\textbf{Solution:}
$(\forall x) (R(x) \implies S(x))$}

\smallspace
\ppart  \onept All 6.042 TAs are monkeys.

\solution{\medskip
\textbf{Solution:}
$(\forall x) (Q(x) \implies P(x))$}

\smallspace
\ppart  \onept No 6.042 TA comes from the 23rd century.

\solution{\medskip
\textbf{Solution:}
$(\forall x) (Q(x) \implies \neg R(x))$}

\smallspace
\ppart  \pts{4} Does (d) follow logically from (a), (b), and (c)?  If so, give
a proof.  If not, give a counterexample.

\solution{\medskip
\textbf{Solution:}

\begin{center}
\begin{tabular}{ll}
        $Q(x) \implies P(x)$ & from (c) \\
        $P(x) \implies \neg S(x)$ & from (a) \\
        $\neg S(x) \implies \neg R(x)$ & from contrapositive of (b)\\ 
        $\therefore Q(x) \implies \neg R(x)$
\end{tabular}

\end{center}

}

\smallspace\smallspace
\ppart  \onept Translate into English:
$(\forall x) (R(x) \vee S(x) \implies Q(x))$.

\solution{\medskip
\textbf{Solution:}
Anyone who is from the 23rd century or  likes to eat pizza is a 6.042 TA.}

\smallspace
\ppart   \onept Translate into English: $(\exists x) (R(x) \wedge
\neg Q(x)) \implies (\forall x)(P(x) \implies S(x))$.

\solution{\medskip
\textbf{Solution:}
If there is a person from the 23rd century who is not a 6.042 TA then all monkeys like to eat pizza}

\solution{
Some students forgot leading quantifiers in the first parts (especially
$\forall x$). On the last part, many students mistakenly said that
the entity mentioned in the first `if' would be a monkey that liked
pizza. Note that this is not the same as the correct statement.
}

\smallspace
\end{problemparts}

\nextproblem

\problem\pts{10}  \textbf{Induction}
% Simple Induction

Prove {\bf by induction} (other methods will not receive credit) that
\[
1 + 3 + 5 + \cdots + (2n-1) = n^2
\]
for all natural numbers $n \geq 1$.

\solution{
Let $P(n)$ be $1 + 3 + 5 + \cdots + (2n-1) = n^2$.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove $\forall n \in N, P(n)$  (by induction on n).\\
1. (Base) $n=1$: $2\cdot1-1=1=1^2$\\
2. (Inductive Step)  $\forall n \geq 0 (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $1 + 3 + 5 + \cdots + (2n-1) = n^2$ \\
\> 3. $1 + 3 + 5 + \cdots + (2(n+1)-1) = (n+1)^2$ \\
\> \> 1. $1 + 3 + 5 + \cdots + (2(n+1)-1) =$  \\
\> \> \> $(1 + 3 + 5 + \cdots + (2n-1)) + (2n+1)$  \> \> Sum with extra term,\\
\> \> \> \> \> Associativity of addition \\ 
\> \> 2. $1 + 3 + 5 + \cdots + (2(n+1)-1) = n^2 + (2n+1)$ \> \> \> Inductive
hypothesis $P(n)$, (2.2.1)\\ 
\> \> 3. $1 + 3 + 5 + \cdots + (2(n+1)-1) = (n+1)^2$ \> \> \> Algebra\\
\> 4. QED \> \> \> \> Implication, UG \\
3. QED  \> \> \> \> \> Induction 
\end{tabbing}

A minority of students treated $P(n)$ as an algebraic expression
rather than a boolean one.  They asserted statements of the form:
$P(n) + (2n+1) = P(n+1)$.  These collections of symbols got little credit.
}

\nextproblem
\problem\pts{10}  \textbf{Induction}

% Strong Induction
Let $G_0=1$, $G_1=2$, $G_2=4$ and define $G_n = G_{n-1} +2G_{n-2} + G_{n-3}$ for $n \geq 3$. \\

Show by induction that $G_n\leq(2.2)^n$ for all $n \geq 0$.

\solution{
\begin{proof}
(Base Cases)\\
$n=0$: $1 = 2.2^0$\\
$n=1$: $2 < 2.2^1 = 2.2$\\
$n=2$: $4 < 2.2^2 = 4.84$\\
(Inductive Step) \\
Assume $P(n)$ for all $k$ such that $0 \leq k \leq n$.
\begin{eqnarray*}
G_{n+1} &=& G_n +2G_{n-1} + G_{n-2} \\
&\leq& (2.2)^n + 2(2.2)^{n-1} + (2.2)^{n-2}\\
&=& (2.2)^{n-2} [(2.2)^2 + 2(2.2) + 1]\\
&=& (2.2)^{n-2} [(2.2 + 1)^2]\\
&=& (2.2)^{n-2} (3.2)^2\\
&=& (2.2)^{n-2} (10.24)\\
&<& (2.2)^{n-2} (10.648)\\
&=& (2.2)^{n-2} (2.2)^3\\
&=& (2.2)^{n+1}\\
\end{eqnarray*}
\end{proof}

One common error in this proof was not doing the proper base cases.  Students also had problems using the strong inductive assumptions.  Note that points were also deducted for not adequately showing that $(3.2)^2<(2.2)^3$.
}

\nextproblem
\problem\pts{10}  \textbf{Structural Induction}

Recall from class the following recursive definition of the set~$F$
    of \emph{binary trees:}
    
    \begin{enumerate}\itemsep 0\baselineskip
    \item A single node is in~$F$.
    \item $\forall t \in F (\mbox{makeleft}(t) \in F)$ 
    \item $\forall t \in F (\mbox{makeright}(t) \in F)$     
    \item $\forall t,t' \in F (\mbox{makeboth}(t,t') \in F)$
    \end{enumerate}

Recall also the definition of the number of nodes $n$ in a tree:
\begin{enumerate}\itemsep 0\baselineskip
\item A single node tree has one node
\item $n(\mbox{makeleft}(t)) = 1+n(t)$
\item $n(\mbox{makeright}(t)) = 1+n(t)$
\item $n(\mbox{makeboth}(t,t')) = 1+n(t)+n(t')$
\end{enumerate}

Consider also the following recursive definition of the height $h$ of a
binary tree:
\begin{enumerate}\itemsep 0\baselineskip
\item The height of a single node is 0
\item $h(\mbox{makeleft}(t)) = 1+h(t)$
\item $h(\mbox{makeright}(t)) = 1+h(t)$
\item $h(\mbox{makeboth}(t,t')) = 1+\max(h(t),h(t'))$
\end{enumerate}

Prove that a binary tree of height $h$ has at most $2^{(h+1)}-1$ nodes. 

\solution{
Base Case: For any tree of height 0, there is at most 1 node. Therefore $2^{(0+1)}-1 = 1 \geq 1$\\
Inductive Step:\\
\begin{itemize}
\item Case 1: $\mbox{makeleft}(t)$\\
\begin{eqnarray*}
n(\mbox{makeleft}(t)) &=& n(t) + 1\\
&\leq& (2^{h(t)+1} - 1) + 1\\
&\leq& 2 \cdot (2^{h(t)+1} - 1) + 1\\
&=& 2 \cdot (2^{h(t)+1}) - 2 + 1\\
&=& 2^{h(\mbox{makeleft}(t)) + 1} - 2 + 1\\
&=& 2^{h(\mbox{makeleft}(t)) + 1} - 1
\end{eqnarray*}

since $h(t) + 1 = h(\mbox{makeleft}(t))$\\.
Thus $n\mbox{makeleft}(t) \leq 2^{h(\mbox{makeleft}(t))+1} - 1$.

\item Case 2: $\mbox{makeright}(t)$\\
Similar to Case 1.

\item Case 3: $\mbox{makeboth}(t,t')$\\
\begin{eqnarray*}
n(\mbox{makeboth}(t,t')) &=& n(t) + n(t') + 1\\
&\leq& (2^{h(t) +1} - 1) + (2^{h(t') + 1} - 1) + 1\\
&\leq& 2 \cdot (2^{max(h(t), h(t')) +1} - 1) + 1\\
&\leq& 2 \cdot ( 2^{h(\mbox{makeboth}(t,t'))} - 1) + 1\\
&=& 2^{h(\mbox{makeboth}(t,t')) + 1} - 2 + 1\\
&=& 2^{h(\mbox{makeboth}(t,t')) + 1} - 1
\end{eqnarray*}

since $max(h(t), h(t')) + 1 = h(\mbox{makeboth}(t,t'))$\\.
Thus $n(\mbox{makeboth}(t,t')) \leq 2^{h(\mbox{makeboth}(t,t'))+1} - 1$.
\end{itemize}

Points were taken off for simply relying on one's intuitive idea of a binary
tree without working from the makeleft, makeright, makeboth definitions, since
the definitions were explicitly given in the problem. Some students
failed to realize that getting a new tree from makeboth involves two 
(possibly distinct) trees. Also, some students reversed the logic of
the induction; i.e., wrote down the inequality they were trying to
prove and manipulated it into the inductive assumption; the direction
of steps should go from the inductive assumption to the statement
being proved.
}

\nextproblem
\problem\pts{10}  \textbf{Relations}

State whether each of the following is an {\bf Equivalence Relation},
{\bf Partial Order}, {\bf Total Order} or {\bf None of these} and give
reasons for your answers.

\problempart\pts{3}{
% None of these
The binary relation $R$ on the set \{1,2,3,4\} such that $R$ =
\{(1,2), (4,4), (3,4), (1,4), (2,4), (3,3), (3,2), (1,1), (1,3),
(2,2), (2,3)\} }

\solution{\medskip
\textbf{Solution:}
None of these.  It is not symmetric because it has (1,2) but not (2,1),
so it cannot be an equivalence relation.  And it is not antisymmetric
because it has (2,3) and (3,2), meaning it cannot be a partial or total
ordering.
}

\smallspace

\problempart\pts{3}{
% Equivalence Relation
The relation $xRy$ over the integers such that 2 divides $x-y$.
}

\solution{\medskip 
\textbf{Solution:} 
Equivalence Relation.  It is reflexive because $x-x = 0$ and 2 divides
0.  It is symmetric because $y-x = -(x-y)$ and if 2 divides $(x-y)$ then
2 divides $-(x-y)$.  And it is transitive because $(x-y)+(y-z) = (x-z)$
meaning if 2 divides $(x-y)$ and 2 divides $(y-z)$ the 2 must divide
$(x-z)$.
}

\smallspace

\problempart\pts{4}{
% Total Order
The relation $xRy$ over all words in this sentence such that $x$ does
not appear after $y$.  (Consider $x$, $y$, and $xRy$ to be words.)  
}

\solution{\medskip
\textbf{Solution:}
Total Order.  It is reflexive because each word does not appear after
itself.  It is antisymmetric because for any two words, $u$ and $w$,
if $u$ does not appear after $w$ and $w$ does not appear after $u$,
they must appear in the same place, ie be the the same word ($u=w$).
And it is transitive because if a word $u$ does not appear after $v$,
and $v$ does not appear after $w$, then $u$ must also also not appear
after $w$.  In addition, every two words are related since one of them
must not appear after the another, thus making it a total order.

Common areas in this part of the quiz included getting the definitions 
of equivalence relations and partial orders confused (especially on the 
symmetric/antisymmetric part).  Also, some students did not realize that
you must have a partial order to have a total order.
In order to recieve full credit, you must have come up with the right category
and have given the right reasons for it.  If you gave some of the correct
properties, you did recieve some partial credit.


}


\nextproblem
\problem\pts{10}  \textbf{More on Relations} 

\ppart\pts{5} List the nodes in the following graph in some order such
that no node points to a node that occurs before it in the list.

\begin{figure}[htbp!]
 \centerline{\resizebox{!}{1.5in}{\includegraphics{figs/topsort}}}
\end{figure}


\smallspace

\solution{\medskip
\textbf{Solution:}

One possible ordering byt a topological sort is A, B, C, G, H, F, E,
D.

} \ppart\pts{5} Explain whether or not we can give such an ordering if
we add an arrow from node E to node A.

\solution{\medskip
\textbf{Solution:}

We cannot give such an ordering since we now have $A \rightarrow B
\rightarrow H \rightarrow E \rightarrow A$ which is a cycle.

}


\nextproblem
\problem\pts{15}  \textbf{Graphs} 

% Spring 95 Quiz 1
The {\em complement} of an undirected graph $G=(V,E)$ is the graph 
$G^c=(V,E^c)$. 
That is, $G^c$ contains exactly those edges that are not in $G$. 

\ppart\pts{5} What are the connected components of the following graph
$H$?:\\ $H=\bigl(\{A,B,C,D,E,F\},\, \bigl\{\{A,F\}, \{B,D\},
\{B,E\}, \{C,D\}, \{C,E\}, \{D,E\}\bigr\}\bigr)$

\solution{
\textbf{Solution:} 
The connected components are {[G1],[G2]}.

\begin{figure}[htbp!]
 \centerline{\resizebox{!}{1.5in}{\includegraphics{figs/prob6a}}}
\end{figure}

}

\smallspace

\ppart\pts{5}  Draw the complement of H.

\solution{
\textbf{Solution:} 

\begin{figure}[htbp!]
 \centerline{\resizebox{!}{1.5in}{\includegraphics{figs/prob6b}}}
\end{figure}
}

\smallspace

\ppart\pts{5} Prove that if an undirected graph~$G$ is not connected
then $G^c$ is.

\solution{
\textbf{Solution:} 

  Suppose $G=(V,E)$ is not connected.  Then $G$ can be divided into
  nonempty disjoint connected components $G_1, G_2, \ldots G_k$ (where
  $k>1$).  Consider any two vertices $a, b$ in $V$.  Let's show that they
  are connected by a path in $G^c$.
\begin{description}

\item[Case 1]  \ $a$ and $b$ are in different connected components of
$G$.  Then there is no edge in $E$ connecting $a$ and $b$.  Thus $G^c$
contains an edge connecting $a$ and $b$.

\item[Case 2]  \ $a$ and $b$ are in the same connected component of
$G$.  Let $c$ be a vertex in a different connected component.  By case
1, $a$ and $c$ are connected, as are $b$ and $c$.  Thus $a$ and $b$ are
connected through $c$.

\end{description}
Thus $G^c$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $G^c$ is connected.

\paragraph{Comments} Most people got parts (a) and (b) correctly. These were intended to give you some intuition on how $G^c$ relates to $G$ and help you answer part (c). Few people got full credit on part (c). Many confused the definition of a connected graph with that of a \emph{fully} connected graph, even thought they had gotten part (a) right! \par Many assumed that using induction was the way to go. Not very surprisingly, given the prominent role that this method has been given in the first part of the course. Unfortunately, in this case, induction doesn't work. Those who did get it right using induction basically used the argument presented in the solution, which makes the inductive argument superfluous. The most common issue in incorrect inductive attempts involved \emph{buildup errors}.
\par Others attempted to prove the claim \emph{by contradiction}. While this made their life slightly more difficult, some actually succeeded. The most common mistake using this approach was the failure to examine the case that two vertices come from the \emph{same connected component} in the original graph.
\par Only a handful of students used the straightforward approach presented in the solutions.    
                                                                                               

}

\nextproblem 
\problem\pts{15}  \textbf{State Machines} 
%% Fall 2000 Problem Set 5 - Modified

A long time ago, in a 2-dimensional galaxy far, far away, everything
was laid out in a 1000 by 1000 meter square.  Han Solo lived at grid
point $(0,0)$ of the square, and Princess Leia lived at grid point
$(0,1000)$.  Of course, Han and Leia wanted to meet, at {\em
exactly\/} the same point in the square.  However, both were
restricted by their rather strange space ships to move according to
very particular rules: Han could only move $3$ units parallel to the
$x$ axis, or 3 units parallel to the $y$ axis, or $3$ units parallel
to the $x$ axis and 3 units parallel to the $y$ axis (all at once,
making a diagonal move).  Leia could only move $3$ units, and only
parallel to either the $x$ axis or $y$ axis.  They do not have to move
at the same time, nor alternating.

\ppart\pts{5}

Model Han and Leia and their possible moves as a (single) state
machine.  That is, define the states $Q$, the start state $Q_0$, and the
transitions $\delta$.

\solution{
\medskip
\textbf{Solution:}
\begin{description}
\item $Q = \{ (H_x, H_y, L_x, L_y) \mid H_x, H_y, L_x, L_y \in \{ 0,
\ldots, 1000 \} \}$, where $(H_x, H_y)$ and $(L_x, L_y)$ are the
positions of Han and Leia, respectively.
\item $Q_0 = \{ (0, 0, 0, 1000) \}$
\item $\delta: (H_x, H_y, L_x, L_y) \mapsto (H_x + 3a, H_y + 3b, L_x + 3c,
L_y + 3d)$, where \\
$(a, b, c, d) \in \{
(1,0,0,0),(-1,0,0,0),(0,1,0,0),(0,-1,0,0),(1,1,0,0),(1,-1,0,0),$\\
$(-1,1,0,0),(-1,-1,0,0),(0,0,1,0),(0,0,-1,0),(0,0,0,1),(0,0,0,-1) \}$
\end{description}
(A common error here was to say that $Q = \{ (a, b, c, d) \mid a, b,
c, d \in \{ 0, \ldots, 1000 \} \}$, without saying what the four
numbers in a state actually correspond to.)}

\smallspace

\ppart\pts{10}
 
Prove formally (using an invariant) that no sequence of moves can
yield a meeting between Han and Leia.

\solution{
\medskip
\textbf{Solution:}
Our invariant is: ``For any reachable state $q = (H_x, H_y, L_x, L_y)$, 
$H_x + H_y - L_x - L_y \equiv 2 \pmod{3}$.''

For notational convenience, let $r(q) = H_x + H_y - L_x - L_y$.  For
the only possible initial state~$q_0$, $r(q_0) = -1000$, so $r(q_0)
\equiv 2 \pmod{3}$.  For any $(q,q') \in \delta$, we note that
$r(q')-r(q)$ is always a multiple of~$3$. Hence, for any $(q,q') \in
\delta$, $r(q) \equiv 2 \pmod{3}$ implies $r(q') \equiv 2 \pmod{3}$.
By the Invariant Theorem, this implies that $r(q) \equiv 2 \pmod{3}$
for every reachable state~$q$.

We now prove that the invariant implies that Han and Leia can never
meet. Suppose, for a contradiction, that Han and Leia can meet in some
state~$q$. That would imply that $r(q) = 0$. However, we just showed
that $r(q)$ can never be~$0$ in a reachable state, which yields a
contradiction.

(Common errors in this problem: Using the Invariant Theorem without
saying so; Not proving that the invariant implies that Han and Leia
can never meet.)}


\end{problems}

\end{document}


After graduating from MIT, you are hired by a startup company that
specializes in organizing frog races.  Your first assignment is to
plan the finals for a race near Johnstown, Pa.  The competition is run
in two stages.  First, some prelimnary races are run between small
groups of the frogs.  Then, the results of those races are used to
determine the frogs' starting positions for the final, deciding race.
All the preliminary races have been run with the following results:


\begin{center}
\begin{tabular}{l|c|c|c|c}
  & Race 1 & Race 2 & Race 3 & Race 4 \\ 
\hline
  1st & Lars & Ivan & David & Ray \\
  2nd & Ray & Josh & Lars & George \\
  3rd & Kavita & Tina & Ivan & Tina \\
  4th & Be & Be & Joe & Joe
\end{tabular}

\end{center}



You must line the 10 frogs up for the final race so that no frog is
after a frog it has beaten in one of the preliminary rounds.  Give one
possible ordering.

\solution{\medskip
\textbf{Solution:}

Two possible orderings are:

David, Lars, Ivan, Josh, Ray, George, Tina, Joe, Kavita, Be

and

David, Lars, Ray, Kavita, George, Ivan, Josh, Tina, Be, Joe

}
