Searching a Treasure
7 is the least number of questions that you can ask to guarantee to find the treasure.

the idea of binary search

Every time when we ask a question, we try to reduce the maximum number of unit squares left to search as small as possible. That is, try to cut the number as nearly to a half as possible. This is the idea as binary search.

the binary search on a row or column of cells

Each unit square of the given grid is called a cell. 

Whenever we are left with some number of cells that are contiguous on the same row or column, we can simulate binary search on those cells with questions on some $n$ by $n$ squares. For example, suppose the treasure is among the cells marked by "t".

$$\begin{array}{|c|c|c|c|c|}\hline
&amp;&amp;&amp;&amp;\\\hline
\phantom{t}&amp;t&amp;t&amp;t&amp;t\\\hline
&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;\\\hline
\end{array}$$

We can ask whether the treasure is in the following square marked by the question marks.

$$\begin{array}{|c|c|c|c|c|}\hline
&amp;&amp;&amp;&amp;\\\hline
\phantom{?}&amp;?&amp;?&amp;\phantom{?}&amp;\phantom{?}\\\hline
&amp;?&amp;?&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;\\\hline
\end{array}$$

If the answer is yes, then we have restricted the range to search to the two "$t$"-cells to the left; otherwise, to the two "$t$"-cells to the right. Continuing this way, we can accomplish binary search on a row of cells or on a column of cells.

the full scheme

First ask whether it is inside the 6 by 6 square at the bottom right corner. 

If yes, ask whether it is inside the 4 by 4 square at the bottom right corner.


If yes, ask whether it is inside the 3 by 3 square at the bottom right corner.


If yes, ask whether it is inside the 2 by 2 square at the bottom right corner.


If yes, we have 4 unit square left. Ask another 3 questions to find it.
Otherwise, it must be at one of the following cells.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
\phantom{t}&amp;\phantom{t}&amp;\phantom{t}&amp;
\phantom{t}&amp;\phantom{t}&amp;t&amp;t&amp;t\\\hline
&amp;&amp;&amp;&amp;&amp;t&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;t&amp;&amp;\\\hline
\end{array}$$
Now choose the following square to ask to determine whether it is on the top row of that 3 by 3 square except the top left cell. If yes, we are left with 2 cells on the same row; otherwise we are left with 3 cells on the same column. Now start binary search.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;?&amp;?\\\hline
\phantom{t}&amp;\phantom{t}&amp;\phantom{t}&amp;
\phantom{t}&amp;\phantom{t}&amp;\phantom{t}&amp;?&amp;?\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
\end{array}$$
Otherwise, it must be at one of the following cells.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
\phantom{t}&amp;\phantom{t}&amp;\phantom{t}&amp;
\phantom{t}&amp;t&amp;t&amp;t&amp;t\\\hline
&amp;&amp;&amp;&amp;t&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;t&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;t&amp;&amp;&amp;\\\hline
\end{array}$$
Now choose the following square to ask to determine whether it is on the top row of that 4 by 4 square except the top left cell. If yes, we are left with 3 cells on the same row; otherwise we are left with 4 cells on the same column. Now start binary search. 
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;?&amp;?&amp;?\\\hline
&amp;&amp;&amp;&amp;&amp;?&amp;?&amp;?\\\hline
\phantom{t}&amp;\phantom{t}&amp;\phantom{t}&amp;
\phantom{t}&amp;\phantom{t}&amp;?&amp;?&amp;?\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;\\\hline
\end{array}$$


Otherwise, ask whether it is inside the 5 by 5 square at the bottom right corner. 


If yes, inquire an appropriate square to determine whether it is on the top row of that 5 by 5 square except the top left cell. If yes, we are left with 4 cells on the same row; otherwise we are left with 5 cells on the same column. Now start binary search.
Otherwise, inquire an appropriate square to determine whether it is on the top row of that 6 by 6 square except the top left cell. If yes, we are left with 5 cells on the same row; otherwise we are left with 6 cells on the same column. Now start binary search.



Otherwise, ask whether it is inside the 7 by 7 square at the bottom right corner.


If yes, inquire an appropriate square to determine whether it is on the top row of that 7 by 7 square except the top left cell. If yes, we are left with 6 cells on the same row; otherwise we are left with 7 cells on the same column. Now start binary search.
Otherwise, inquire an appropriate square to determine whether it is on the top row of the original 8 by 8 square except the top left cell. If yes, we are left with 7 cells on the same row; otherwise we are left with 8 cells on the same column. Now start binary search.


Why cannot we succeed with less than 7 questions?

Since after the first question, one of the yes or no answer will leave us at least $\min(64-5^2, 6^2)=36$ cells to search. Each question can cut the maximal number of cells to search at most in half. Since $2^5=32 &lt; 36$, we need at least another $5+1=6$ questions to guarantee success.

Open problem

Does the scheme above reach the minimum average number of questions, assuming the treasure can be in any cell with equal probability? 

I believe it does. However, I am not able to obtain a complete proof as it is not clear how to reduce the many cases to a manageable level.

Exercise

What is the least number of questions to guarantee to find the treasure that is in one of the cells of a 7 by 7 grid?