Un peón se mueve a través de $n\times n$ chesssboard así que en un movimiento que puede cambiar una plaza a la derecha, una plaza de arriba, o a lo largo de una diagonal hacia abajo y a la izquierda. Puede el peón ir a través de todos los cuadrados del tablero, visitando cada una exactamente una vez, y terminar su viaje en el cuadro a la derecha de la inicial?
Tengo entendido que esto significa que los siguientes son los tres válido mueve V para el peón P:
------------- | | V | | ------------- | | P | V | ------------- | V | | -------------He demostrado que esta situación es imposible de esta manera: dejar que el peón se mueve de arriba, a la derecha, en diagonal a la izquierda - ser representados por vectores en el plano 2D, respectivamente: $\hat{A}=(0,1),~\hat{B}=(1,0),~\hat{C}=(-1,-1)$, entonces la combinación lineal $a\hat{A}+b\hat{B}+c\hat{C}=(1,0)$, que es el necesario desplazamiento neto para el peón. Así vemos que $a=c$ e $b=c+1$. Así, el número total de movimientos es $a+b+c=3c+1$, que sabemos que debe ser igual a $n^2-1$. Por lo tanto, $n^2=3c+2$ que sabemos que es imposible integral de la $c,n$.
Sin embargo, nuestra Profe nos quiere hacer esta pregunta a través de propiedades invariantes en su lugar. He probado a hacer la paridad de la suma de las coordenadas invariante. Sin embargo, los cambios incluso en movimiento a derecha o de arriba, mientras que sigue siendo igual en movimiento en diagonal. Por lo tanto, esta propiedad no puede ser invariante. También traté de pensar de las distancias del punto de origen, la paridad de la diferencia de coordenadas, ...sin éxito.
Lo invariante de la propiedad que me estoy perdiendo? (sólo sugerencias, por favor)
Respuesta
¿Demasiados anuncios?
Ya que la única manera para moverse a la izquierda o a la baja sea la diagonal (de donde el peón es la plaza que se encuentra a su izquierda y uno hacia abajo) que el número de tales movimientos se $k.$ Ahora supongamos que el peón termina uno a su derecha, no hay ninguna neta hacia arriba o hacia abajo movimiento, mening el número de arriba se mueve también es $k.$ Ya que también termina una plaza a su derecho, debe de ser uno más a la derecha de mover a la izquierda mover, yo.e $k+1,$ ya que hay $k$ izquierda se mueve y la necesidad de $k+1$ derecha se mueve a acabar uno a la derecha de inicio.
Por lo tanto el número total de movimientos es $3k+1.$ Ahora ya que es un $n \times n$ plaza hay $n^2-1$ se mueve en el tour. (Nota: este es un camino recorrido no cerrado tour ya que queremos dejar un cuadrado a la derecha de inicio). Conclusión $3k+1=n^2-1$ o $n^2=3k+2.$ Pero no cuadrado es $2$ mod $3.$ por Lo que no se puede hacer.
Si tratamos de aterrizaje de un cuadrado a la izquierda del punto de inicio, podemos igualmente a la conclusión de $n$ debe ser divisible por $3.$ yo no tengo ningún argumento para descartar que fuera, pero después de todo lo que no era preguntado por la cuestión. Sospecho que no hay ningún tipo de paseos, incluso para $n$ un múltiplo de $3.$
