\author{Problem Author: Suhas Nagar}
\newcommand{\treasurehuntheader}{Problem K: Treasure Hunt}

\begin{frame}{\treasurehuntheader{}}
  \begin{block}{Problem}
    \begin{itemize}
      \item Given a 5x5 grid, locate a 2x2 square of treasure using at most 5 queries.
      For each query you may ask if a given location contains treasure.
    \end{itemize}        
  \end{block}
\end{frame}
\begin{frame}{\treasurehuntheader{}}
  \begin{block}{Solution}
    \begin{itemize}
      \item If we know the treasure is in a 3x3 area centered at $(i, j)$,
      we can determine its location in 2 queries, for example by querying
      $(i-1, j)$, then either $(i-1, j-1)$ or $(i, j-1)$ depending on
      the result of the first query.
      \item We can locate which 3x3 subgrid the treasure is in by querying 3
      locations among $\{(2,2), (2,4), (4,2), (4,4)\}$ to determine which
      of those 4 locations is the center of the 3x3.
      \item In total this takes 3+2=5 queries in the worst case.
    \end{itemize}        
  \end{block}
\end{frame}
