Combinatorics: Treasure hunt problem on a $10 × 10$ board

Question

In two adjacent $1 \times 1$ fields in a $10\times10$ board are two treasure chests. You have to guess where are these two treasure chests. In every move you can get the information(is there a treasure chest in that field) about only one field. What is the minimum number of moves that you need to discover these two chests using a certain strategy(worst case scenario)?

Answer 1

First, instead of talking about two chests that are adjacent, I will treat the two chests as one 1x2 chest that covers two adjacent squares.

Consider these 50 tries:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline \end{array}

I am bound to get a 'hit' with one of those, but in the worst-case scenario I haven't gotten a hit after 49 of those, and so as long as I make sure to leave a corner for last, that would mean:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline &&X&&X&&X&&X&\\ \hline \end{array}

But this only leaves two possible positions for the chest, so one more guess, and I know: 50 guesses.

OK, but what about getting to this case:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline &&C&&X&&X&&X&\\ \hline \end{array}

Well, now I need 2 more guesses, so 49 + 2 is 51 guesses. So, maybe worst-case scenario is 51? No, because I didn't do this very cleverly. I should have left both corners for last:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline &X&&X&&X&&X&&\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline &&X&&X&&X&&X&\\ \hline \end{array}

If I don't get a hit for these first 48 guesses, then pick a corner for the 49-th guess to figure out which corner it is in, and then 1 more guess will tell me the exact location of the chest: 50 guesses.

If I do get a hit on the 48-th guess, which I made sure was along a side:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline &X&&X&&X&&X&&\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline X&&X&&X&&X&&X&\\ \hline &X&&X&&X&&X&&X\\ \hline &&C&&X&&X&&X&\\ \hline \end{array}

then I need at worst 2 more guesses to figure it out, so 50 guesses again.

Of course, getting a hit before the 48-th guess will mean that you need 50 or less total guesses as well.

So, with the basic strategy of picking the X's as indicated, leaving the two corners for last, and making sure that the 48-th guess is along a side, 50 guesses is the worstcase for this strategy.

Finally, there is no strategy whose worstcase takes less than 50 tries. to prove that, we will prove by induction over $n$ that for any $n>2$ it is true that for any $P_n$ (A graph consisting of $n$ vertices and $n-1$ edge that connects all vertices along one long path) you need at least $\lfloor n/2 \rfloor$ tries for a worstcase scenario to figure out the location of the chest, assuming the chest is located along an edge, i.e. located at two adjacent vertices:

Base: We have two base cases:

$n=3$: Since the chest has two possible locations, it will take at least 1 guess, and $\lfloor 3/2 \rfloor =1$ . Check!

$n=4$: If you guess a vertex at the end, and you get a miss, then you need at least 1 other guess. If you guess one of the other two vertices, and you get a hit, then there are still two possible locations for the chest, so again you need 1 other guess. So, either way, the worst case takes two guesses, and $\lfloor 4/2 \rfloor =2$. check!

Step:

Consider $P_n$. In the worst case scenario you have to guess either one of the vertices at the end or second-to-the-end, because if youdon't guess any of those, then there are at least two possible locations left for the chest (namely at either end of the path). If you guess a vertex at the very end, and you get a miss, the by inductive assumption you need at least $\lfloor (n-1)/2 \rfloor$ additional guesses for the worstcase to figure out the location of the chest, for a total of $1+\lfloor (n-1)/2 \rfloor$ guesses, and $1+\lfloor (n-1)/2 \rfloor \ge \lfloor n/2 \rfloor$. If you guess a second-to-the-end vertex and you get a miss, then by inductive assumption it will take at least $\lfloor (n-2)/2 \rfloor$ additional guesses in the worstcase, for a total of $1+\lfloor (n-2)/2 \rfloor = \lfloor n/2 \rfloor$ guesses. So, either way, it takes at least $\lfloor n/2 \rfloor $ guesses in the worst case to figure out the location of the chest in a $P_n$.

Since in any graph that contains a $P_n$ as a subgraph the chest can be located along an edge of this $P_n$, it follows that for any graph that contains a $P_n$ subgraph it will take at least $\lfloor n/2 \rfloor$ guesses to locate the chest in such a graph.

Finally, if we consider the graph for a 10x10 board where every square is a vertex any any two vertices are connected if and only if the corresponding squares are adjacent, then we note that this graph contains a $P_{100}$ subgraph, since there exists a path of length 100 that visits each of the vertices (in the board, you can just start in a corner and spiral in, for example). Therefore, given that the chest is again located along an edge in this graph, we find that in the worst case it will take $\lfloor 100/2 \rfloor =50$ guesses.

So, there is no strategy whose worst case gives less than 50 guesses, and since we identified a strategy whose worst case is 50 guesses, the miminum of the worst case is exactly 50.

So: 50 it is!

Answer 2

So, here's the high-level idea. First, let's think about what it takes to locate even one of the treasures. Think of the 10x10 board as a graph $G$ with vertices the cells and an edge between every two adjacent cells. Recall that a vertex cover is a set of vertices such that each edge in the graph is adjacent to some of them.

Now, clearly, the number of vertices $c$ in the smallest vertex cover of $G$ is a lower bound on the number of cells we need to examine, since if we examine less than $c$ cells, there might be an edge out there both of whose cells we haven't touched yet, and the treasures could be there.

So a reasonable strategy appears to be: take a smallest vertex cover of $G$ and check the vertices there. However, we then run into the problem of determining where the second treasure is, since that might require a variable amount of additional cells to examine. Indeed, if we locate one of the treasures in a corner square, we need to check at most 2 other squares for the other square, while if we locate it in an inner square with 4 neighbors, we might need to check 4, and we've been ignoring this cost in our analysis.

The solution is to schedule our traversal of the minimum vertex cover in a way that the bad vertices (degree 4) get traversed before the degree-3 vertices which in turn get traversed before the degree-2 vertices. This gradual decay of the degrees makes sure that we never need more than $c+1$ questions, because in the worst case we need one vertex cover's worth of cells ($c$) plus at most one more cell, since at this point there are either:

• 2 possibilities for the second treasure;
• 3 possibilities and one has already been examined;
• 4 possibilities and two have already been examined;

and examining one of the unexamined two possibilities will tell us with certainty where the second treasure is. In effect, we're processing the potentially bad vertices before the worst-case bound has kicked in.

On the other hand, any strategy needs at least $c+1$ cells, because otherwise any minimal vertex cover would be enough to deduce where the second treasure is, whereas it's easy to make an example of one that doesn't.

Thus the answer is $c+1$, where $c$ is the size of the minimum vertex cover of $G$, provided that there exists a minimum vertex cover of $G$ with the property that it has at least one vertex of degree 2,3 and 4 - which is easy to check.