5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jun 12 at 15:01
  • $\begingroup$ @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. $\endgroup$ – Navjot Waraich Jun 12 at 16:05
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus Jun 12 at 16:22
6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – lox Jun 13 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.