The 16th Japanese Mathematical Olympiad - The Final Round

By walking one block from one intersection to another, the sum of the coordinates changes its parity. Since there are totally $mn-1$ blocks in the way, $(m,n,a,a^{\prime },b,b^{\prime })$ must satisfy one of the followings: (1) $mn$ is odd, and both $a+b$ and $a^{\prime }+b^{\prime }$ are even, or (2) $mn$ is even, and one of $a+b$ and $a^{\prime }+b^{\prime }$ is odd and the other is even. However, even if (1) or (2) holds, there are no such paths if one of the followings are satisfied (see Fig. 1): (3) $m=2$ and $1\ne b=b^{\prime }\ne n$, or (4) $m=3,n$ is even, ($b^{\prime }-b>1$ or $a=a^{\prime }=2$) and • $a+b$ is odd and $b<b^{\prime }$, or • $a+b$ is even and $b>b^{\prime }$. Figure 1: These examples satisfy (3) or (4), so there is no such paths.

Now we take arbitrary $(m,n,a,b,a^{\prime },b^{\prime })=(\hat{m},\hat{n},\hat{a},\hat{b},{\hat{a}}^{\prime },{\hat{b}}^{\prime })$ satisfying $\star$ and prove, by induction, the existence of a path with the required conditions. $\star$ (1) or (2) satisfied, and neither (3) nor (4) satisfied. For $\hat{n}\le 3$, see Fig. 2. Let $\hat{n}>3$ and assume, as presumption of the induction, that such paths exist for $(m,n)=(\min \{\hat{m},\hat{n}-2\},\max \{\hat{m},\hat{n}-2\})$ and any $a,b,a^{\prime }$ and $b^{\prime }$ satisfying $\star$. Figure 2: When $(\hat{m},\hat{n})=(2,2),(2,3)$ or $(3,3)$, the positions of $(a,b)$ and $(a^{\prime },b^{\prime })$ are the same as one of those in the figure, allowing rotation and reversing. In any cases in the figure, there exists a path satisfying the required conditions. When both $\hat{b}$ and ${\hat{b}}^{\prime }$ are greater than 2, excluding the cases mentioned in Fig. 3, there is a path which passes all the intersections on third to $m$-th avenue exactly once, because of the presumption of the induction. Since such paths always contain some part of the third avenue, one can expand that part as Fig. 4 and get a path which satisfies the required conditions. One can prove similarly the case both $\hat{b}$ and ${\hat{b}}^{\prime }$ are less than $n-1$. Reversing the direction if necessary, we may assume $\hat{b}\le 2$ and ${\hat{b}}^{\prime }\ge \hat{n}-1$. Reversing the whole town if necessary, we may assume $\hat{a}+\hat{b}$ is even. Start from $⟨\hat{a},\hat{b}⟩$ and go to $⟨2,1⟩$ via all the intersections on the first and second avenue. Walk one block to the east. From that intersection, because of the presumption of the induction, there is a path to $⟨{\hat{a}}^{\prime },{\hat{b}}^{\prime }⟩$ via all the rest intersections.

Figure 3: The positions of $(a,b)$ and $(a^{\prime },b^{\prime })$ which don't meet $\star$ if the two avenues are removed from the west are the case in the figure, and the upside-down version of it. In both cases in the figure, there are a way satisfying the conditions in the problem. Figure 4: Expand a block of the third avenue.