patternMinor
Searching a Treasure
Viewed 0 times
searchingtreasurestackoverflow
Problem
I was selected for a UG interview 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?
"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?
Solution
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.
-
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.
Otherwise, ask whether it is inside the 7 by 7 square at the bottom right corner.
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, a
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, a
Context
StackExchange Computer Science Q#110588, answer score: 6
Revisions (0)
No revisions yet.