Combinatorics: Treasure hunt problem on a $10 × 10$ board 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)?

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.
