几个世纪前，海盗船长黑板在 $M \times N(2 \leq M, N)$ 网格结构的岛屿上的一个单元格中埋藏了一大笔宝藏。你和你的船员已经到达了岛屿，并带来了特殊的宝藏探测器来找到藏有宝藏的单元格。对于每个探测器，你可以设置它扫描一个特定的子网格 $[a, b] \times[c, d]$，其中 $1 \leq a \leq b \leq M$ 和 $1 \leq c \leq d \leq N$。运行探测器会告诉你宝藏是否在该区域内，但它不能说明宝藏在该区域的具体位置。你计划设置 $Q$ 个探测器，这些探测器只能在所有 $Q$ 个探测器都准备好后同时运行。用 $M$ 和 $N$ 表示，最少需要多少个 $Q$ 才能保证你的船员可以确定黑板传奇宝藏的位置？
Let $m=\left\lceil\frac{M}{2}\right\rceil$ and $n=\left\lceil\frac{N}{2}\right\rceil$. We claim that the minimal $Q$ is $m+n$. For the construction, start with $m$ detectors covering $[i, i+m-1] \times[1, N]$ for $1 \leq i \leq m$. For every pair of rows, there is a detector that covers one row but not the other, hence this determines the row of the treasure. Similarly, placing $n$ detectors covering $[1, M] \times[i, i+n-1]$ for $1 \leq i \leq n$ determines the column, and thus the location of the treasure.

For the bound, we require the following lemma.
Lemma. A $1 \times k$ island requires at least $\left\lceil\frac{k}{2}\right\rceil$ detectors.
Proof. Consider the $k-1$ lines separating the cells. If one of these lines is not covered by any detector, then these cells are indistinguishable. Similarly, if neither of the vertical lines at the ends are covered, then the first and last cells are indistinguishable. In particular, at least $k$ vertical lines need to be covered by the detectors. A detector covers 2 vertical lines, giving the result.

In general, consider the first row. Since the cells are distinguishable, by the lemma there must be at least $n$ detectors that intersect it non-trivially (as in, cover between 1 and $N-1$ of the cells). The analogous result holds for the last row and the first/last columns, giving $2 m+2 n$ detectors, where a detector may be counted multiple times.

If a detector intersected at least three of these sets, say it intersected the first row and the first and last columns. Therefore it covers the entire width of the island, and does not actually distinguish any cells in the first row, contradiction.

Therefore each detector contributes to at most 2 of the above $2 m+2 n$ detectors, giving the final lower bound of $\frac{2 m+2 n}{2}=m+n$ detectors required, as desired.