The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$.

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$.

So, I manage to find the smallest value which is $2N$ and it can be realised with drawing all diagonal parallel to each other. Why it can not be smaller?

We can observe this configuration as a planar graph with $2N$ horizontal and $2N$ vertical edges on the border of the table and $N^2$ diagonal edges, so we have overall $E=4N+N^2$ edges. Also this graph has $4N$ vertices on the border of the table and some, say $r$ vertices in the interior of the table, so we have $V = 4N+r$ vertices. Clearly $r\leq (N-1)^2$. We are interested in the number of bounded faces of this graph. Since this graph is not necesary connected we have to use general Euler formula $$V-E+F = c+1$$ where $c$ is a number of a connected components. Since $c \geq 1$ the number

\begin{eqnarray} K & = & F-1\\ & = & E-V+c\\ & = & (4N+N^2)-(4N+r)+c\\ & = & N^2-r+c\\ &\geq & N^2-(N-1)^2+1\\ & = & 2N \end{eqnarray}

Now I would like to find also the largest value using Euler's formula but I can not find easly an estimate for $c$ which would do. Some idea?

Anyway, the answer is $K_{\max} = \Big[{(N+1)^2 +1\over 2}\Big]$

Each of the $4N$ exterior edges is a side of exactly one face and every other of at most two. So the sum of the sizes of faces is equal to at most $2N^2+4N$. Now, each face has to be at least quadrilateral except corner faces which can be triangles but there are at most $4$ of them taking at most $12$ from $2N^2+4N$. So altogether there can be at most: $$\frac{2N^2+4N-12}{4}$$ Non-triangular faces and therefore at most: $$\frac{2N^2+4N-12}{4}+4=\frac{(N+1)^2+1}{2}$$ Faces in total. Equality is achieved if for each diagonal we alternate directions.

You also don't have to use Euler's formula in order to prove that there are at least $2N$ sides. Imagine that these diagonals are actually mirrors and we emit light from the midpoint of each external edge in direction perpendicular to it (into the square's interior). It's easy to see that such beam of light can't end up in a loop so it has to end entering another external edge. Also, given such path one can easily reconstruct the placement of the mirrors and therefore the boundary of the region that the beam travels through. It follows that each region has either $0$ or $2$ external edges and therefore at most two so there are at least $2N$ regions.