Número mínimo de movimientos para llegar a una celda en un tablero de ajedrez por un caballero

Question

Dado un tablero de ajedrez infinito representado como un 2D plano Cartesiano. Un caballero se coloca en el origen. ¿Cuál es el mínimo número de movimientos que necesita para llegar a una celda $(m,n)$? (Sin pérdida de generalidad, podemos asumir que el $m$ $n$ son no negativos números enteros.)

Answer 1

Después de un poco de garabatos, me he convencido a mí mismo de lo siguiente:

Para llegar al origen en el menor número de movimientos, siempre que el movimiento (o uno de los movimientos) que lleva más cercano al origen, que no es (0,1), (2,2), o un reflejo de una de estas células.

Tal vez después de un poco más de los garabatos, voy a venir con algún tipo de prueba.

Actualizado para responder a la pregunta: Si lo anterior es cierto, entonces podemos proceder de la siguiente manera:

Podemos suponer $m \ge n$. A continuación, repetimos el movimiento $(-2,-1)$ hasta llegar a la diagonal o la $x$-eje (me estoy quedando en la película hacia atrás aquí, de$(m,n)$$(0,0)$).

Si $m \ge 2n$, esto se lleva a $n$ se mueve, y termina en $(m-2n,0)$.
Si $m \le 2n$, esto se lleva a $m-n$ se mueve, y termina en $(2n-m,2n-m)$.

Tan sólo necesitamos saber cuántos movimientos se requiere de la diagonal o la $x$-eje.

Por la diagonal, el número de movimientos para llegar desde $(x,x)$ al origen es $$2\lfloor \frac{x+2}{3}\rfloor $$ excepto por la anómala punto de $(2,2)$, lo que requiere de 4 movimientos, no 2. Pero a menos que nuestro punto de partida fue $(2,2)$, podemos ignorar esta anomalía $-$ procede de un punto a a $(4,3)$, no vamos a $(2,2)$, pero a $(3,1)$, la cual requiere de 2 movimientos.

Para el $x$-eje, la cantidad de maniobras necesarias para llegar de $(x,0)$ al origen es $$x - 2\lfloor\frac{x}{4}\rfloor$$

excepto por la anómala punto de $(1,0)$, la cual requiere de 3 movimientos, no 1. Pero a menos que nuestro punto de partida fue $(1,0)$, podemos ignorar esta anomalía $-$ procede de un punto a a $(3,1)$, no vamos a $(1,0)$, pero a $(1,2)$, lo que requiere 1 mueva.

A partir de esto, es fácil construir una fórmula explícita, si es lo que usted quiere, usted sólo tiene que tratar los puntos de partida $(2,2)$ $(1,0)$ como casos especiales.

Answer 2

Las respuestas se tabulan aquí en la Enciclopedia en Línea de Secuencias de Enteros. Una fórmula es también la hay, pero tiene un recursiva de componente: $m$ $n$ al menos 2, se da a la $$T(m,n)=1+\min(T(m-2,n-1),T(m-1,n-2))$$ Se podría trabajar sobre convirtiendo esto en una forma cerrada.