\documentclass[12pt]{article}

\newtheorem{claim}{Claim}
  
\usepackage{fullpage}
\begin{document}
\begin{center}
\textbf{CS 141} \\ Advanced Topics in Algorithms \\ Spring 2004 \\
Problem Set 6a \\ Due Wednesday, February 25
\end{center}

\begin{enumerate}

 \item \textbf{[30 Points]  The Absent-Minded Professor.}
Professor Juan I. Dalean of the Massachusetts Institute of Zymurgy walks
out of his building one evening.  Unfortunately, he can't remember if he
parked his car up the street or down the street.  Moreover, a combination of thick fog, poor street lighting,
 and the effects of zymurgical laboratory work have rendered it impossible for Professor~Dalean to recognize his car until he is actually standing at the point at which the car is parked.

More precisely, imagine that Professor Dalean's office is at the origin of
 a line.   The car is parked someplace on the line
some \emph{integer} distance away from the origin.
An optimal offline algorithm
would know the location of the car and would proceed directly there. 
An online algorithm doesn't know the position and must therefore search
for it.  The online algorithm is $k$-competitive if it eventually finds
the car and traverses a total distance no larger than $k$ times the distance
traversed by the online algorithm.

Find a competitive online algorithm for this problem and carefully show
that competitive ratio is 9.

\end{enumerate}
\end{document}