Utilizar el principio de invariabilidad para demostrar que no se puede alcanzar una coordenada

Question

El problema: Un robot deambula por una cuadrícula bidimensional. A partir de $(0, 0)$ Se le permiten 4 tipos de pasos diferentes:

1. $(+2, -1)$
2. $(+1, -2)$
3. $(+1, +1)$
4. $(-3, 0)$

Está tratando de llegar a $(0, 2)$ .

(a) Describa una máquina de estados de este problema.

(b) ¿Será capaz de llegar a $(0, 2)$ ? Encuentre un camino que lo lleve allí o utilice el principio invariante para demostrar que no existe tal camino.

En primer lugar, no estoy del todo seguro de lo que es el principio invariante. En segundo lugar, lo que tengo como una descripción de la máquina de estado:

Estado inicial ::= $(0, 0)$

Transiciones ::= $\{(x, y) \to (x+2, y-1)\} \cup \{(x, y) \to (x+1, y-2)\} \cup \{(x, y) \to (x+1, y+1)\} \cup \{(x, y) \to (x-3, y)\}$

Hasta ahora todo lo que tengo es mi argumento de que para llegar a $(0, 2)$ el robot debe llegar primero a una coordenada $q$ de manera que si $(0, 2)$ es $r$ entonces $q \to r$ . Por lo tanto, si puede llegar a una coordenada que puede llegar a $(0,2)$ por lo que puede llegar a $(0,2)$ . Hice los 4 casos, y encontré que $(-2, 3), (-1, 4), (-1, 1), (3, 2)$ todos pueden llegar a $(0, 2)$ en un solo movimiento. Sin embargo, como había tantos pasos diferentes, no encontré una forma de llegar a esos 4 (o 5) espacios en una cantidad razonable de movimientos de adivinar y comprobar, ni pude ver un patrón claro. Supongo que tengo que demostrar que no existe tal camino, pero no estoy seguro de cómo.

Answer 1

Una pista: Cuando el robot está en $(x,y)$ , dejemos que $f(x,y)$ sea el resto cuando $x-y$ se divide por $3$ . Demuestra que cada vez que el robot da un paso, $f(x,y)$ no cambia (permanece invariable).

Answer 2

El robot puede ir a posiciones $(x,y)$ donde $x-y$ es un múltiplo de 3 solamente. Obsérvese que este invariante se mantiene en el origen, y se conserva en cada uno de los cuatro pasos. Como $(0,2)$ no satisface esta propiedad, el robot no puede llegar.