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
&&&&\\\hline
\phantom{t}&t&t&t&t\\\hline
&&&&\\\hline
&&&&\\\hline
&&&&\\\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
&&&&\\\hline
\phantom{?}&?&?&\phantom{?}&\phantom{?}\\\hline
&?&?&&\\\hline
&&&&\\\hline
&&&&\\\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.
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 < 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?
