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
31.03.2018 15:25
Part (a.) and this problem are quite similar.
02.04.2018 03:01
04.04.2018 17:44
Edit: Thanks to @below for pointing out.
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.