\problemdata                                                             
        {Ordering - Frog Race} % latex-friendly label for the prob.
        {Topological Sort} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Final, 1} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
\renewcommand{\arraystretch}{1} 
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 preliminary 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 up the 10 frogs 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


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

}
\end{problem}                                 