Puede un caballero de la visita de cada campo en un tablero de ajedrez?

Question

Yo estaba haciendo ejercicios sobre teoría de grafos y me encontré con un muy interesante ejercicio (que probablemente tenga algo que ver con el Ciclo Hamiltoniano): "Es posible que con el paso de cada campo de un 4x4 o 5x5 tablero de ajedrez sólo una vez y volver al punto de partida el uso de un caballero?" ¿Alguien tiene alguna idea de cómo hacer frente a este problema? Estoy más interesado en un esquema de cómo hacerlo o sólo algunas sugerencias.

Answer 1

SUGERENCIA:

$$\begin{array}{|c|c|c|c|} \hline \cdot&&&\\ \hline &&\cdot&\\ \hline &\cdot&&\\ \hline &&&\cdot\\ \hline \end{array}$$

Answer 2

Para el $5 \times 5$ tablero de ajedrez, se pinta los cuadrados en blanco y negro en un tablero de ajedrez de la moda. Hay $b:=\lfloor 5^2/2 \rfloor$ cuadrados de un color (por decir negro) y $w:=\lceil 5^2/2 \rceil$ plazas del otro color (blanco).

Es importante destacar, que el caballero se mueve siempre de negro a blanco o a negro. Por lo tanto, para que exista un cerrado caballero de la gira, necesitamos el número de $b=w$. Sin embargo, $b<w$, por lo que no hay cerrado caballero de la gira de este consejo.

Answer 3

Sugerencia: debe entrar y salir de cada cuadrado. Mirar en las esquinas. Lo que es especial acerca de ellos?

Answer 4

Así que yo estaba rozando a través de las preguntas que yo me he preguntado aquí y me acordé de que he encontrado una solución diferente a mi pregunta. Aquí está:

Si es posible que un caballero a paso en cada campo de un tablero de ajedrez, que significa que hay un Hamiltionian Ciclo en un gráfico, en el que un vértice es un equivalente a un cuadrado en el tablero de ajedrez y los bordes entre los vértices de responder a la posibilidad de un movimiento de un caballero entre las plazas. Hay un teorema que dice que si eliminamos un conjunto V de k vértices en un Grafo Hamiltoniano, entonces hay exactamente k de los componentes de gráfico de $G-V$. Así que si nos quite los cuatro vértices en el centro obtendríamos 4 vértices aislados y el resto de la gráfica - total de 5 componentes, lo que se contradice con la hipótesis de que G es Hamiltoniano.

$$\begin{array}{|c|c|c|c|} \hline \cdot&&&\cdot\\ \hline &\cdot&\cdot&\\ \hline &\cdot&\cdot&\\ \hline \cdot&&&\cdot\\ \hline \end{array}$$

Answer 5

Hay una animación que muestra que es posible: http://d24w6bsrhbeh9d.cloudfront.net/photo/aOqebpR_460sa.gif (Me gustaría dejar un comentario, yo no tengo la suficiente reputación)