Caballo en un tablero de ajedrez moviéndose de a1 a h8

Question

Me han dado un acertijo para resolver que dice: ¿Puede un caballo comenzar en la casilla a1 de un tablero de ajedrez, e ir a la casilla h8, visitando cada una de las casillas restantes una vez en el camino?

Razoné que esto no será posible porque las casillas a1 y h8 tienen el mismo color ( digamos, negro ). Si no tenemos en cuenta estas casillas, el tablero de ajedrez restante tiene 62 casillas, lo que significa que hay 30 casillas negras y 32 casillas blancas. Si el caballo visitara cada una de estas casillas exactamente una vez, entonces esto significaría que tendríamos la secuencia WBWBWB.....W donde el par "WB" estaría ocurriendo 31 veces. Sin embargo, esto no es posible ya que hay dos blancos más que negros. Cuando presenté esta solución, me dijeron que era incorrecta, pero no me dieron ninguna explicación. ¿Pueden ayudarme?

Answer 1

Puede haber una explicación más sencilla: para visitar todas las casillas sin volver a ninguna se necesitan 63 pasos, un número impar, pero cada paso cambia el color, por lo que no se puede terminar en el mismo color que se empezó.

Tal vez te hayan suspendido porque has dado una respuesta correcta diferente a la que buscaba el evaluador.

Answer 2

Tu idea es correcta. Tu explicación podría pulirse un poco, pero no veo por qué debería ser incorrecta.

Answer 3

Convertir su pregunta en una lengua.

L = { (wb)^i, 32>=i>=1,i pertenece a Q}

con Gramática :

S->wA
A->bS
A->b

No es una solución exacta, porque te han dicho que ninguna casilla es visitada dos veces, lo que no he podido traducir a la lengua de arriba.

No conozco la solución porque acabo de empezar a estudiar los gráficos y los árboles, pero estoy seguro de que el problema puede resolverse matemáticamente utilizando un gráfico o un lenguaje, o quizás ambos combinados.