Baltic Way 2023 Shortlist

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$, $$\begin{gathered} 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. \end{gathered}$$