XXIV OBM

Consider the center of the $mn$ unit squares and connect two centers if the numbers assigned to the correspondent squares are consecutive. Then we obtain a path with $mn-1$ unit segments. The $mn$ centers determine a lattice with $(m-1)(n-1)$ unit squares. Squares with numbers $k$ and $k+3$ correspond to a lattice square with three unit segments:



So we need to prove that there is a lattice square with at least $3$ segments. Suppose the contrary, so the number of segments is at most $2(m-1)(n-1)$, in which border segments are counted once and the interior segments are counted twice. The path uses at most $2(m-1)+2(n-1)-1=2m+2n-5$ segments on the border. So there are at least $mn-1-(2m+2n-5)=mn-2m-2n+4$ interior segments. Hence the path uses $2m+2n-5+2(mn-2m-2n+4)=2mn-2m-2n+3>2(m-1)(n-1)$ lattice segments (counting repetitions), a contradiction.