Solution:

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 $2m+2n$ 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 $2m+2n$ detectors, giving the final lower bound of $\frac{2m+2n}{2}=m+n$ detectors required, as desired.

Solution:

The following alternative approach from CMO competitor Marvin Mao of Bergen County Academies is another full solution.

Take the same construction as in Solution 1. For the bound, consider the following sets:

- $S_{\mathrm{CR}} := \{\{(1,1),(1,N)\},\{(M,1),(M,N)\}\}$, i.e. the pairs of corners on the same row;
- $S_{\mathrm{CC}} := \{\{(1,1),(M,1)\},\{(1,N),(M,N)\}\}$, i.e. the pairs of corners on the same column;
- $S_{\mathrm{R}} := \{\{(x,i),(x,i+1)\} : x \in \{1, M\}, 1 \leq i \leq N-1\}$, i.e. the pairs of adjacent edges on the first/last row;
- $S_{\mathrm{C}} := \{\{(i,x),(i+1,x)\} : 1 \leq i \leq M-1, x \in \{1, N\}\}$, i.e. the pairs of adjacent edges on the first/last column.

For each detector, we assign it a score $\left(x_{\mathrm{CR}}, x_{\mathrm{CC}}, x_{\mathrm{R}}, x_{\mathrm{C}}\right)$, where $x_{\mathrm{i}}$ is the number of pairs of cells in $S_{\mathrm{i}}$ for which the detector covers exactly one of the two cells. The possible scores of the detectors are as follows:

This is equal to $\left\lceil\frac{M}{2}\right\rceil + \left\lceil\frac{N}{2}\right\rceil$ except if both $M, N$ are odd. In this case, if there is at least one more detector, then we have the required bound, so assume otherwise. In particular, we must achieve exactly the score $(2,2,2N-2,2M-2)$, with each detector contributing 4 to the total component sum.

In particular, to fill out the first two components, we must either have two detectors scoring $(1,1,1,1)$, or two detectors scoring $(2,0,2,0)$ and $(0,2,0,2)$. This yields a total score of $(2,2,2,2)$, leaving us with achieving exactly $(0,0,2N-4,2M-4)$ from the rest. Since we cannot have a non-zero score in the first two entries and must have a total component sum of 4, we can only use detectors scoring $(0,0,4,0)$ or $(0,0,0,4)$. But $2N-4, 2M-4 \equiv 2 \pmod{4}$, which is a contradiction.

Therefore all situations require at least $\left\lceil\frac{M}{2}\right\rceil + \left\lceil\frac{N}{2}\right\rceil$ detectors.