# Searching a Treasure

I was selected for a UG interview for computational natural science program and the following was one of the questions asked:

"Suppose we have an $$8 \times 8$$ grid. Under one of the blocks, I (the interviewer) have hidden a treasure which you have to find by asking questions to me. The questions are to be of the form - "Is it under this $$n \times n$$ square (where $$n \le 8$$)?" For each question, I charge you some money and you have a finite amount with you. What is the least number of questions that you can ask to find where the treasure is?

I don't have any background in high school computer science and while discussing this problem with a senior, I discovered that the problem relates to "complexity" in computer science. Can somebody help me with this as a beginner?

• If you can ask about arbitrary rectangles then you can perform binary search, and figure out the location of the treasure in 6 questions. This is easily shown to be optimal. – Yuval Filmus Jun 12 at 15:01
• @YuvalFilmus how can binary search work here? How is the comparison done for middle value? I think the question whether the treasure is under nth x nth block does not give indication to what subset of grid to eliminate by binary search. – Navjot Waraich Jun 12 at 16:05
• @NavjotWaraich The way I understood it is - you choose an arbitrary square sub grid and ask about it. If instead of a square you could ask about arbitrary rectangles, then you can easily perform binary search. – Yuval Filmus Jun 12 at 16:22

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.

• 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 &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline \phantom{t}&\phantom{t}&\phantom{t}& \phantom{t}&\phantom{t}&t&t&t\\\hline &&&&&t&&\\\hline &&&&&t&&\\\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 &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&?&?\\\hline \phantom{t}&\phantom{t}&\phantom{t}& \phantom{t}&\phantom{t}&\phantom{t}&?&?\\\hline &&&&&&&\\\hline &&&&&&&\\\hline \end{array}$$

• Otherwise, it must be at one of the following cells. $$\begin{array}{|c|c|c|c|c|c|c|}\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline \phantom{t}&\phantom{t}&\phantom{t}& \phantom{t}&t&t&t&t\\\hline &&&&t&&&\\\hline &&&&t&&&\\\hline &&&&t&&&\\\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 &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&?&?&?\\\hline &&&&&?&?&?\\\hline \phantom{t}&\phantom{t}&\phantom{t}& \phantom{t}&\phantom{t}&?&?&?\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\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 < 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?

• Nice approach! I wonder about the lower bound; if there was an option "no treasure", then it would be quite easy to prove a lower bound of 7 with decision trees. However, this is not the case here! – lox Jun 13 at 21:11