VN IMO Booklet

We number the rows $1$ to $m+1$ from left to right, the columns $1$ to $n+1$ from top to bottom and suppose that the point $A$ is $(1,1)$ (at the top left of the board).

a. Necessary condition: The route can be written as a letter sequence consisting of $L,R,U$ and $D$, which respectively represents left, right, up and down direction. Since there are $(m+1)(n+1)$ intersections, the length of the sequence is $(m+1)(n+1)$.



Since the route starts at $A$ and returns to $A$, it follows that the number of left turns is the same as the number of right turns and the number of up turns is equal to the number of down turns. In other words, the number of letter Ls is the same as the number of letter Rs, as well as the number of letter Us and the number of letter Ds are equal. This implies $(m+1)(n+1)$ is even. Thus $m$ is odd or $n$ is odd.

Sufficient condition: Without loss of generality, suppose that $m$ is odd. We will construct the route by the following rules:

The first horizontal movement: we start at $A$, go through the columns $1$ to $n$. Every vertical movement is only one unit; if we move horizontally, move between columns $2$ and $n$. The last horizontal movement: move from column $n$ to $1$, then move vertically to $A$.

This process can be done since $m$ is odd. We reach the conclusion of (a).

b. Consider two intersections at each of which there is a turn and the distance between those two turns are the closest ($A$ is also counted as an intersection). Between the two intersections, there is a horizontal or vertical route.

Let $r$ be the number of horizontal sub-routes of the route, $c$ be the number of vertical sub-routes of the route and $k$ be the number of turns (not counted at $A$). We will prove the following remarks.

Remark 1. $k+1=2r=2c$.

Proof. For each intersection at which there is a turn, there is exactly one horizontal sub-route and vertical sub-route. The number of turns, also counted at $A$, is also the number of non-ordered pairs of the form

(horizontal sub-route, vertical sub-route)

where the horizontal sub-route and vertical sub-route intersects at some intersection. Moreover, each horizontal sub-route has common intersections with exactly two vertical sub-routes, and similarly each vertical sub-route has common intersections with exactly two horizontal sub-routes, thus

$$k+1=2r=2c.$$

To find the least value of $k$, we only need to find the least value of $r$ and $c$.

Remark 2. $r\ge m+1$ or $c\ge n+1$.

Proof. Suppose that $r\le m$, then there is a row on which each intersection lies on some vertical sub-route, which implies $c\ge n+1$. Similarly, if $c\le n$ then $r\ge m+1$.

We consider the following cases:

If $m$ is odd, $n$ is even: suppose $r\le m$, by the above remark, there is a row on which each of $n+1$ intersections lies on some vertical sub-route, but since there is an odd number of intersections on this row, we cannot return to $A$, a contradiction. Thus $r\ge m+1$ and $k=2r-1\ge 2m+1$. We can construct a route with exactly $m+1$ vertical sub-routes similarly to (a). Therefore, $\min k=2m+1$.

If $m$ is even, $n$ is odd: following the same pattern, we have $\min k=2n+1$.

If $m,n$ are odd: Equalities occur in the inequalities $r\ge m+1$ and $c\ge n+1$, which implies that

$$\min k=2\min (m,n)+1.$$

In conclusion,

If $m,n$ are odd then $\min k=2\min (m,n)+1$. If $m$ is even and $n$ is odd then $\min k=2n+1$. * If $m$ is odd and $n$ is even then $\min k=2m+1$.