Problem
Suppose you are given a map divided into a $n \times n$ grid of squares. You know that somewhere on the map a mine of the ore necessary for curing a wide range of cancers is represented by a $k \times k$ square. You can send $m$ drones to any square on the map to take a sample and determine whether the sector belongs to the mine, after which the drone self-destructs. What is the minimum number $m$ of drones you have to send to establish the location of the mine?
Key Question
Given a $n\times n$ square grid, find the minimum number $m$ of guesses necessary for determining the position of a $k\times k$ square on the grid.
Minimal Objective
Solve the problem for $n=10001$, $k=7000$.
General Objective
Solve the problem for any $k$ and $n$ such that $k < n$.
Prove rigorously that the $m$ you have found is indeed minimal.
Solution Idea
Let's colour the squares belonging to the mine as blue.
Looking at each axis of the grid, determine the corner squares of the mine by the variant of a binary search. Let's start looking, for example, at the horizontal axis.
If $\log_2(\frac{n}{k}) = \lg(\frac{n}{k}) > 1$, we know that the square at the position $\lfloor \frac{n+1}{2} \rfloor$ definitely belongs to the mine. In general, in that case we only need to start guessing in the segments of length $n-k$ from each edge point of the side. If, however, $\lg(\frac{n}{k}) \leq 1$, this optimisation loses its power.
More generally, we can divide the axis into $\lceil \frac{n}{k} \rceil$ parts and sample squares, taking, for instance, first squares of the segments, and testing whether they are coloured or not, moving from left to right. If we find a coloured square, we can try to conduct a binary search in the last segment before the segment in which the coloured square was found. For this, divide this segment in two parts and test the middle square. If it is not coloured, recurse into the right half. If it is coloured, recurse into the left half. The last found square is then a corner square.
Repeating the procedure for the vertical axis, we can then find the $(x, y)$-coordinates of a corner. Testing at most 3 neighbouring squares, we can then determine the position of the entire mine, since we know $k$.
Could you please tell me whether this line of reasoning is correct, and does it lead to the minimal solution? How would you make it rigorous?