37th Iranian Mathematical Olympiad

We claim the answer is $mn-n$.

First note that by Pick's theorem, the area of a region is at least $\frac{b}{2}-1$, where $b$ is the number of the lattice points on its boundary. Obviously, for any region, $b\ge 3$ and if $b=3$, the region must be a triangle. But each of the edges of this triangle lie between two consecutive rows of the grid, which is impossible. So by Pick's theorem, the area of a region is at least $\frac{4}{2}-1=1$.

Consider the $2n$ small segments of length 1 in the top and the bottom edges of the grid. We will prove that for each of these segments, we can assign a triangle inside the grid with the area of $\frac{1}{2}$, counted in the infinite region, such that this segment is an edge of the triangle, and we can choose these triangles in a way that none of them intersect.

Label the points of the first row as $a_1,a_2,\dots ,a_n$, and the points of the second row as $b_1,b_2,\dots ,b_n$. For all $1\le i\le n$, let $t_i$ be the greatest index such that $a_i$ and $b_{t_i}$ are connected by a segment (if it exists). If $a_i$ isn't connected to any of the $b_j$s and $i>1$, let $t_i=t_{i-1}$, and if $a_1$ isn't connected to any of the $b_j$s, let $t_1=1$. Clearly, $t_1\le t_2\le \cdots \le t_n$, which means for all $i\ne j$, $a_i{b}_{t_i}$ and $a_j{b}_{t_j}$ do not intersect. Also the segment $a_i{b}_{t_i}$ doesn't intersect with any of the other drawn segments. Now assign triangle $△a_{i-1}{a}_i{b}_{t_i}$ to the segment $a_{i-1}{a}_i$. The area of this triangle is $\frac{1}{2}$ and it is counted in the infinite region. Also none of such triangles intersect. Similarly, we can assign such triangles to the $n$ segments of the last row of the grid.

So the area of the grid counted in the infinite region is at least $2n\times \frac{1}{2}=n$. This means that the sum of the areas of finite regions is at most $mn-n$. Because the area of each region is at least 1, there can be at most $mn-n$ finite regions.

For the equality, consider the grid below. Obviously, the area of the grid counted in the infinite region is $n$ and the area of each finite region is 1. So there are $mn-n$ finite regions and we're done. ■