, 2023

Answer: The solution is $n^2 + 2n - 3$.

Combining the x-bound and the y-bound, we get in both cases the upper bound $n^2 + 2n - 2$. This can still be improved by observing that it is not possible to satisfy both bounds with equality. For $n = 2k + 1$, in order to get $n^2 - 1$ units in y-direction, the two end points have to be $(0, k+1)$ and $(1, k+1)$ (so that they are never in the smaller part). Without loss of generality, the first step goes from $(0, k+1)$ into the set $\{(1, y) : y \ge k+2\}$. Then, if we always want to change the x-coordinate and also always move between $y \ge k+2$ and $y \le k+1$ (which we have to do in order to make the y-bound tight), we can only alternate between $\{(1, y) : y \ge k+2\}$ and $\{(0, y) : y \le k\}$. Similarly, for $n = 2k$, without loss of generality, the first step goes from $\{(0, y) : y \le k\}$ to $\{(0, y) : y \ge k+1\}$, and if we don't want to lose anything in x- or y-direction we can only alternate between these two sets.

$$2k + 2 \sum_{y=1}^{k} (n - 2y) - 1 + 2 \sum_{y=k+2}^{n} (2y - n - 1) = 4k^2 + 4k - 1 = n^2 - 2,$$
and for $n = 2k$,
$$k + k + \sum_{y=1}^{k-1} [(n - 2y) + (n - 2y + 1)] + \sum_{y=k+2}^{n} [(2y - n - 2) + (2y - n - 1)] \\ = 4k^2 - 2 = n^2 - 2.$$