In a $m\times n$ square grid, with top-left corner is $A$, there is route along the edges of the grid starting from $A$ and visits all lattice points (called "nodes") exactly once and ending also at $A$. a. Prove that this route exists if and only if at least one of $m,\ n$ is odd. b. If such a route exists, then what is the least possible of turning points? *A turning point is a node that is different from $A$ and if two edges on the route intersect at the node are perpendicular.
Problem
Source: 2018 Vietnam Team Selection Test
Tags: combinatorics, graph theory, square grid
gausskarl
31.03.2018 15:25
Part (a.) and this problem are quite similar.
gausskarl
02.04.2018 03:01
Color the grid black, white alternatively. Then the route will also be "alternate": right after a white point is a black point and vice versa. Since the start and the end have the same color, the route must contain an odd number of nodes, or $(m+1)(n+1)+1$ is odd. This implies immediately at least one of $m,\ n$ is odd.
In the converse, it is straight-forward to see a route in that case. For example, if we give the nodes its coordinate, with $A=(0,0)$ and the bottom-right is $(m, n)$ and $n$ is odd , there is this route:
$$\begin{matrix}
(0,0)&\leftarrow &(0,1)&\leftarrow &(0,2)&\leftarrow &\cdots &\leftarrow &(0,n)\\
\downarrow &\ &\ &\ &\ &\ &\ &\ &\uparrow\\
(1,0)&\ &(1,1)&\rightarrow&(1,2)&\ &\cdots&\ &(1,n)\\
\downarrow&\ &\uparrow &\ &\downarrow &\ &\cdots &\ &\uparrow\\
(2,0)&\ &(2,1)&\ &(2,2)&\ &\cdots &\ &(2,n)\\
\downarrow&\ &\uparrow &\ &\downarrow &\ &\cdots &\ &\uparrow\\
\vdots&\ &\vdots&\ &\vdots&\ &\ddots&\ &\vdots\\
(m,0)&\rightarrow&(m,1)&\ &(m,2)&\rightarrow&\cdots&\rightarrow&(m,n)
\end{matrix}$$
ThE-dArK-lOrD
04.04.2018 17:44
Let say there're $m+1$ vertical lines of points and $n+1$ horizontal lines of points.
For each of such route, it can be divided into some paths, which alternatively between being vertical and horizontal.
Lemma: Either there're at least $m+1$ vertical paths, or there're at least $n+1$ horizontal paths.
Proof: If there're at most $m$ vertical paths, there must be a vertical line of points which no vertical paths passed. And for points on that lines to be passed, we need $n+1$ horizontal paths.
Hence, there is a kind of path that has at least $\min (m,n)+1$ paths.
Not hard to see that this contributes at least $2\min (m,n)+1$ turning points. The construction is easy.
Edit: Thanks to @below for pointing out.
ThE-dArK-lOrD
04.04.2018 19:35
Ok, it's easy to fix, though My post in #6 already show that the answer is $2\min \{ m,n\} +1$ when $\min \{ m,n\}$ is even (with the real easy construction.) So, the case that left is when $\min \{ m,n\}$ is even. From the first part, we get that $\max \{ m,n\}$ must be odd. We'll show that, in that case, the answer is $2\max \{ m,n\} +1$ (with the similar construction.) WLOG $m>n$, i.e. $m$ is odd and $n$ is even. If there're at least $m+1$ vertical lines, we are done (in similar way with the case in #6.) If not, there must be a vertical line of points, called $\ell$, which no vertical paths passed. Note that $\ell$ is not a border of the whole grid. And so, at each of $n+1$ points on $\ell$, there must be a horizontal line passed. Let $\ell$ divided the grid into two disjoint non-empty areas. Consider a particle, start at $A$, moving along the route, which is a cycle. Each time passing through $\ell$, the position it reached switch alternatively between these two areas. But $n+1$ is odd, this makes the particle can't return to $A$ after it passed $\ell$, in total, $n+1$ times. Hence, this sub-case can't happen, done.