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$. [asy][asy] draw((0,0)--(3,0)--(3,3)--(0,3)--cycle); draw((1,0)--(1,3), dotted); draw((2,0)--(2,3), dotted); draw((0,1)--(3,1), dotted); draw((0,2)--(3,2), dotted); draw((1,0)--(0,1)--(2,3)--(3,2)--(2,1)--(0,3)); draw((1,1)--(2,0)--(3,1)); label("$1$",(0.35,2)); label("$2$",(1,2.65)); label("$3$",(2,2)); label("$4$",(2.65,2.65)); label("$5$",(0.35,0.35)); label("$6$",(1.3,1.3)); label("$7$",(2.65,0.35)); label("Example with $N=3$, $K=7$",(0,-0.3)--(3,-0.3),S); [/asy][/asy]
Problem
Source: MEMO 2015, problem T-4
Tags: combinatorics
MellowMelon
29.08.2015 17:33
Minimum: Treat the diagonals as mirrors. There are two kinds of regions: ones that touch the edge and have a horizontal or vertical side, and ones that don't. For the ones that do touch the edge, if we shine a laser straight through that edge and let it bounce off the diagonals, it always eventually exits out of another edge after traversing the entire region. Therefore, exactly two unit segments of the board's boundary are part of each edge-touching region. This means the number of edge-touching regions is always $2N$. This is the smallest value of $K$. We can construct it by orienting all diagonals the same way. Maximum: We use areas and the bound on edge-touching regions above. The number of edge-touching regions is always $2N$. Up to four of these regions can have area $1/2$, and the rest have area at least 1, so these regions occupy an area of at least $4 \cdot 1/2 + (2N - 4) \cdot 1 = 2N - 2$. The regions that do not touch the edge form a closed loop of at least four half triangles and have area at least 2. The maximum area left for regions not touching the edge is $N^2 - 2N + 2$, so there are at most $\left\lfloor \frac{N^2 - 2N + 2}{2} \right\rfloor$ regions that do not touch the edge. So in total, we have at most $\left\lfloor \frac{N^2 + 2N + 2}{2} \right\rfloor$ regions. This is the largest value of $K$. We can construct it by making the top left diagonal cut off a region of area $1/2$, then orienting the remaining diagonals in a checkerboard fashion, where each diagonal has the opposite orientation of the diagonals it is orthogonally adjacent to.