2
$\begingroup$

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$.

enter image description here

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\\ &\geq& (4N+N^2)-(4N+r)+1\\ &\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 an apropriate estimate for $c$ which would do. Some idea?

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

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ A possibly easier way to get the lower bound $2N$: The diagonals cut the $N^2$ squares into $2N^2$ triangles. These are joined to each other along the vertical and horizontal edges. There are $2N(N-1)$ of these edges. So the number of connected components is at least $2N^2-2N(N-1)=2N$. Another way to say this is that the dual graph of your triangulation has $2N^2$ vertices and $2N(N-1)$ edges, and thus at least $2N$ components, with equality iff this dual graph is acyclic. $\endgroup$
    – Andreas Blass
    Commented Jul 9, 2019 at 16:22
  • $\begingroup$ An idea for the upper bound is trying to prove that each component contains at least 4 triangles, unless it touches the boundary in which case it could contain only 2 triangles, or even 1 if it's in the corner (but only in this case). $\endgroup$
    – Del
    Commented Jul 9, 2019 at 20:39
  • $\begingroup$ Sorry, I was talking about faces (or regions in your original question) $\endgroup$
    – Del
    Commented Jul 10, 2019 at 7:37
  • 2
    $\begingroup$ 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. @GerryMyerson $\endgroup$
    – nonuser
    Commented Aug 26, 2019 at 4:52
  • 1
    $\begingroup$ Simultaneously cross-posted on Math.SE and MO: math.stackexchange.com/q/3285966/14578, mathoverflow.net/q/335721/37212. This violates site rules. Please don't do that. $\endgroup$
    – D.W.
    Commented Jun 25 at 17:44

0

Reset to default

You must log in to answer this question.