The answer I think is $\lceil \tfrac{m}{2} \rceil+\lceil \tfrac{n}{2}\rceil$ and I think the idea is to look at the perimeter of the board. I didn't finish this in contest though.

The CJMO equivalent was a $2 \times 4$ grid. I think the idea was related to unique representation in binary, where each detector showed a 0 or 1 for each cell?

Replace $M,N$ with $m,n$. The answer is $\lceil \tfrac{m}{2}\rceil+\lceil \tfrac{n}{2}\rceil$. Obviously it is necessary and sufficient to have each cell to be located within a distinct set of rectangles. For convenience orient the grid so that $(1,1)$ is in the bottom left corner and we have $m$ columns/$n$ rows. Construction: By querying $[k,k+\lfloor \tfrac{m}{2}\rfloor-1] \times [1,n]$ for $1 \leq k \leq \lceil \tfrac{m}{2} \rceil$, each column lies in a unique set of rectangles, hence we can determine the treasure's column. Similarly, querying $[1,m] \times [k,k+\lfloor \tfrac{n}{2}\rfloor-1]$ for $1 \leq k \leq \lceil \tfrac{n}{2}\rceil$ reveals the treasure's row. $\blacksquare$ Bound: Obviously querying $[1,m] \times [1,n]$ does nothing, so we forbid it. Consider $m$ vertical grid edges between $(k,1)$ and $(k+1,1)$ for $1 \leq k \leq m-1$, as well as the edge to the right of $(m,1)$. Also consider the $n$ horizontal grid edges between $(1,k)$ and $(1,k+1)$ for $1 \leq k \leq n-1$, as well as the edge to the top of $(n,1)$. Clearly each rectangle may only overlap at most $2$ of the considered edges, and equality cannot occur if a rectangle contains the "opposite corner" $(m,n)$. On the other hand, every edge not on the border of the grid must lie on the border of some rectangle, otherwise the two cells it borders cannot be distinguished from the queries. Hence if both $(m,1)$ and $(1,n)$ are contained in some rectangle (not necessarily the same) we need all of the selected edges to lie on the border of some rectangle, hence we would need at least $\lceil \tfrac{m+n}{2}\rceil$ rectangles. However, this argument works for any of the four corners of the grid, and since at most $1$ cell can lie in no rectangles, we can pick some corner such that this argument works. Thus we always need at least $\lceil \tfrac{m+n}{2}\rceil$ rectangles. This equals $\lceil \tfrac{m}{2}\rceil+\lceil \tfrac{n}{2}\rceil$ when $mn$ is even, in which case we're done. If $m$ and $n$ are both odd, a bit more work needs to be done. If equality holds in this case and we have exactly $\tfrac{m+n}{2}$ rectangles, then every rectangle must contain exactly $2$ of the considered edges. Suppose that some corner is not covered by any cells—WLOG $(1,1)$. Then in fact every rectangle that overlaps $2$ of the considered edges must overlap either $2$ vertical edges or $2$ horizontal edges. Hence we would need at least $\lceil \tfrac{m}{2}\rceil+\lceil \tfrac{n}{2}\rceil$ rectangles. Thus suppose that every corner cell is in some rectangle, so we can apply the above argument for all four corners. Since equality always holds, it is evident that we need every rectangle to either have width $m$ or height $n$; call the former rectangles fat and the latter skinny, and note that no rectangle is both fat and skinny. Consider some row. Fat rectangles give us no distinguishing information on the cells in this row, so all of the $m-1$ edges between cells in this row must be on the border of some skinny rectangle. At least one of the leftmost/rightmost edges on this row (these lie on the border) also must lie on the border of a skinny rectangle, else the leftmost and rightmost cells are indistinguishable. Hence we have $m$ edges that must lie on the borders of skinny rectangles, hence we need at least $\lceil \tfrac{m}{2}\rceil$ skinny rectangles to intersect it. We may repeat this argument with some column to find that we need at least $\lceil \tfrac{n}{2}\rceil$ fat rectangles intersecting it; since no rectangle is both skinny and fat, it follows that we actually have at least $\lceil \tfrac{m}{2}\rceil+\lceil \tfrac{n}{2}\rceil$ total rectangles, finishing the problem. $\blacksquare$

awesomeming327. wrote: The answer I think is $\lceil \tfrac{m}{2} \rceil+\lceil \tfrac{n}{2}\rceil$ and I think the idea is to look at the perimeter of the board. I didn't finish this in contest though. yeah i also got $\lceil \tfrac{m}{2} \rceil+\lceil \tfrac{n}{2}\rceil$ but wrote an extremely sloppy proof that probably won't get points lol

Very reminding of India EGMO TST 2022/3 unless I'm misremembering.

The answer is $\lceil{\frac{M}{2}}\rceil+\lceil{\frac{N}{2}}\rceil$.The construction is quite: obvious, I'll leave it as an exercise for the reader. Bound: let's consider how can a rectangle intersect with the perimeter. Obviously, it is a union of zero, one or two convex connected figures. Detector distinguishes two adjacent cells if one of them is covered by it and the other one isn't. Now let's dissect all detectors into two categories: first is detectors that cover two segments on opposite sides of the board, the other one are the ones that touch exactly two not-opposite sides and the corner in intersection. Let $A$ be the number of first ones, $B$ - second ones. Then we have not more than $2B+4A$, where $B \geq 2$ because we have $4$ corners that are covered differently. So $4(A+B)-4 \geq 4(A+B)-2B=2B+4A \geq 2(m+n-2)$, so $A+B \geq \lceil{\frac{m+n}{2}}\rceil$. For odd $m,n$ we can easily find that the bound is not tight, which finishes the proof.

Uh shouldn't the answer depend on (b-a), (d-c)? I think those are fixed... (given that the toy example fixed b-a<=2, d-c<=4)

Answer: $Q=\lceil{\tfrac{M}{2}}\rceil+\lceil{\tfrac{N}{2}}\rceil$ Notice that $Q$ does not increase on a smaller board as the same detectors still work on a smaller grid. Thus it suffices to consider the case $M=2m$ and $N=2n$ for the construction and the case $M=2m+1$ and $N=2n+1$ for the bound. Construction: Set up the detectors $[1+i,m+i]\times [1,2n]$ for $0\leq i \leq m-1$ and $[1,2m]\times [1+j,n+j]$ for $0\leq j \leq n-1$. These can determine the row and column that the treasure is located in. Bound: Notice that every interior edge must lie on the perimeter of a detector as to distinguish between the cells on either side and all but possibly one cell must lie in some detector. Now consider the $4m$ vertical edges and the $4n$ horizontal edges that have exactly one point in common with the outer perimeter. We are concerned about three types of detectors. First, a detector that contains exactly one corner which contains one of each such type of edge on its perimeter. Second, a detector that contains two corners along the same side that contain two of one such type of edge on its perimeter. Finally, all other detectors that contain at most four edges of only one type. If we have at least three detectors of any of the first two types then we get a bound of $m+n+2$, otherwise we must have two detctors of the second type going in different directions, leading to the same bound.