¿Cómo pruebo que cualquier tablero de ajedrez de tamaño $n \times 3$, donde n está incluso y $n \geq 10$, tiene un caballero cerrado ' tour s?

Question

Actualmente estoy atascado en un problema de mi ordenador de clase de teoría de la tarea. La pregunta me pide demostrar, mediante la inducción, que cualquier tablero de ajedrez de tamaño $n \times 3$ donde $n$ es incluso y $\geq 10$, se han cerrado caballero de la gira. He trabajado en el problema durante un par de horas, pero parece que no puede encontrar ninguna pista sobre la solución. Ni siquiera puedo averiguar el recorrido por lo que creo que es el caso base, $n = 10$. Consejos y sugerencias en cuanto a cómo podría ir a probar esto?

La pregunta en sí misma viene con una pista, diciendo que habrá dos casos de base. Al principio pensé que esto significaba que yo tendría que mostrar un cerrado del caballero de tour por un valor de $n < 10$, lo que podría darme una ayuda útil a la propiedad durante la inducción paso, pero de haber revisado el artículo de Wiki sobre cerrado caballero tours ahora entiendo que no hay ningún valor de $n < 10$ para que un cerrado caballero del tour es posible. En ese caso, tal vez un caso base de tablero de ajedrez puede ser descompuesto en subchessboards en una forma que revela un cerrado caballero de la gira, que se extiende a algunos valores de $n$, mientras que otro puede ser descompuesta en una forma diferente, que se extiende a algunos otros valores de $n$? No estoy realmente seguro de cómo interpretar la pista y ya no puedo siquiera imaginar una sola cerrado caballero de la gira que efectivamente estoy perplejo.

Algunas de las definiciones que vienen con la pregunta:

En el ajedrez, un caballero del movimiento consiste en viajar dos plazas en una dirección (horizontal o verticalmente, pero no en diagonal) y, a continuación, una plaza en 90 grados a estos.

Cerrado caballero de la tour es una secuencia de caballero movimientos que toque en cada cuadrado del tablero exactamente una vez y en una plaza de la que uno es un caballero alejarse de los principios de la plaza.

No quiero la solución completa para el problema, pero agradecería un poco de ayuda en cuanto a cómo debería de acercarse a ella, ya que actualmente estoy completamente atascado.

Answer 1

Si, vi el % de casos $n=10$y $n=12$ puede encontrarse en el papel de la colina y de Tostado.

Answer 2

Una vez que averiguar la base de casos $n=10$ $n=12$ usted debe demostrar la inducción de paso que es: si hay un cerrado caballero de la gira de la junta directiva del tamaño de la $n\times 3$ hay en la placa del tamaño de la $(n+4)\times 3$. Esto es suficiente para demostrar que el reclamo para todos incluso a $n\geq 10$ puesto que ocupa por tanto de la base de casos.

Sugerencia: Suponga que tiene un cerrado caballero de la gira de la junta directiva del tamaño de la $n\times 3$. En este recorrido hay un movimiento desde la plaza de la $(n-1,3)$ a la plaza de la $(n,1)$ (estoy usando la convención de que la esquina superior izquierda de la plaza se llama $(1,1)$ y el de más a la derecha en la esquina inferior de la plaza se llama $(n,3)$). Ahora quitar este paso de la gira y de imaginar que hay un $4\times 3$ tabla añadida a la derecha de la placa original.

La tarea es visitar todas las plazas de este nuevo $4\times 3$ directorio a partir de la plaza de la $(n-1,3)$ y final a una plaza que se puede mover a $(n,1)$. El primer paso es obvio: es de$(n-1,3)$$(n+1,2)$. Hay dos posibilidades, en las que el último movimiento debe tierra, de modo que se puede mover a $(n,3)$: son$(n+1,3)$$(n+2,2)$. Cuando usted tiene éxito en esta tarea, que ha conseguido sustituir la mudanza $(n-1,3)\to(n,1)$ en el tour original con una cadena de movimientos que cubren el agregado de la pieza de la junta directiva. El resultado es un cerrado caballero de la gira en la junta de tamaño $(n+4)\times 3$ y la inducción de paso se ha completado.

Answer 3

Schwenk base de los casos se pueden encontrar a lo largo del borde derecho de la Fig. 6 de este documento. Dado que las tablas se $3\times 10$$3\times 12$, parece probable que la inducción paso consiste en extender una solución para un $3 \times n$ junta a una solución para un $3\times(n+6)$ junta. Sin embargo, yo no he visto Schwenk argumento, por lo que tomar esto con un grano de sal.

Un lugar diferente enfoque se utiliza en el papel del Caballero de la Gira aquí. Podría ser un poco más fácil. Te voy a dar la idea, sin que ninguno de los detalles.

Los autores encuentran dos disjuntos no cerrado la mitad-tours en un $3\times 8$, comenzando en la esquina superior izquierda y terminando en la esquina inferior derecha, el otro a partir de en la esquina superior derecha y terminando en la esquina inferior izquierda; entre ellos, la cubierta de la junta. Ellos llaman a esto una placa de extensión; cualquier número de estos pueden ser encadenados juntos para hacer más extensión de las tablas. También encontramos lo que ellos llaman la ficha tablas de tamaños $3\times 7$, $3\times 9$, $3\times 11$, y $3\times 13$. Cada una de estas tablas se admite un completo (no cerrada) de la gira que comienza en la esquina superior izquierda y termina en la plaza en diagonal de abajo y a la derecha del punto de partida. Por lo tanto, si la junta de ahora se extiende a la izquierda, sería posible extender el recorrido saltando a la celda inmediatamente a la izquierda de la original de la esquina superior izquierda. No es difícil ver cómo combinar la ficha y la extensión de las tablas para obtener cerrado del caballero tours en las tablas de tamaños de $3\times 2n$$n\ge 7$; el $3\times 10$ $3\times 12$ de los casos se manejan de forma individual.