Shortest path of a knight on a chessboard

Question

Given a knight on an infinite-size chessboard. Knight starts from $(0,0)$ and the destination is $(x,y)$ with $x\ge 0$ and $y\ge 0$. I want to prove that among all the path with the minimum steps, there must be a path only containing points $(a,b)$ with $-1\le a\le x+2$ and $-1\le b\le y+2$. I am not sure whether it is right or not, but after I tried many cases, it seems to be right.

My first attempt is to use mathematical induction to prove that for any $c$, all points within the square $0\le x\le c$ and $0\le y\le c$ satisfy that statement. I could prove my enumeration that $(c,c)$ with $0\le c\le 3$ satisfy the proposition. Then under the assumption that $(c,c)$ with $0\le c\le n$ satisfy the proposition, I want to prove $(c,c)$ with $0\le c\le n+1$ satisfy the proposition, too. I attempted to use the idea of Dijkstra's Algorithm, by stating that all points within the square $0\le c\le n+1$ can be accessed by one step from points within the square $0\le c\le n$, but it seems not a correct proof.

My second attempt is to use linear equation. If $3|x+y$, then intuitively, the knight only needs to jump rightwards and upwards, and it will the fastest way to reach $(x,y)$. Assume the knight go $u$ steps of $(2,1)$ and $v$ steps of $(1,2)$, which leads to a equation$$\begin{cases}2u+v=a\\u+2v=b\end{cases}$$So $u+v=\frac{a+b}{3}$. I guess this must be the minimum steps, but I still have difficulty rigorously proving this statement. I thought by solving equations in this kind will lead me to the answer, but just don't know how to continue. Could anybody offer me some hint or help?

Thank you very much!

Answer 1

Two ideas for proofs:

• First deal with the cases that allow for minimal paths without any step to the right and up; that shouldn’t be too difficult. Then you can assume that there is at least one step to the right and up. Reorder the steps so that this is the first step and use induction to show that the rest of the path can be made minimal with admissible steps.
• Assume that a minimal path goes outside the admissible area, say, horizontally. Rearrange the steps near this violation such as to reduce the horizontal violation. Once you’ve removed all horizontal violations, do the same thing for vertical violations. The difficult part is ensuring that this doesn’t create new horizontal violations.

These are of course just sketches, with some details to be filled in, and I’m not sure they can both be made to work, but you only asked for some hint or help.

About your own proof attempt: It’s not true that the knight only has to go to the right and up if $3\mid x+y$. It can only do that if $2x\ge y$ and $2y\ge x$; otherwise it will also have to make some other moves to make up for the discrepancy between $x$ and $y$.