Selectivo de Ibero 2006 P1

[Ivan]

Se dispone de un tablero de [math]n\times n (dividido en casillas de [math]1\times 1) y de un rey. En cada movida el rey se desplaza una casilla, y tiene dos clases de movimientos: de clase [math]I si se desplaza de la casilla que ocupa a una vecina horizontal o vertical; de clase [math]II si se desplaza de la casilla que ocupa a una vecina diagonal (con un solo vértice en común). Además es obligatorio que las movidas consecutivas sean siempre de distinta clase (se deben alternar una movida de cada clase). Hallar todos los enteros [math]n\ge 2 para los cuales es posible elegir una casilla inicial y una secuencia de movidas tales que el rey visite exactamente una vez cada casilla del tablero (se considera que la casilla inicial fue visitada por el rey al iniciar la primera movida).

[Joacoini]

Spoiler: mostrar

Ejemplo generalizable para $n$ par que consta de pegar varias veces la solución para $n=2$.

SIbero2021P1.png

Para $n$ impar pintamos de $4$ colores usando alternadamente dos colores en las filas pares y dos en las impares.
Se puede observar que en los primeros cuatro movimientos (en caso de arrancar moviéndonos horizontalmente empezamos a contar desde el segundo) pasamos por unas casilla de cada color, luego en los siguientes cuatro movimientos tambien vamos a pasar una vez por cada color.
Así que si $A$ y $B$ son la cantidad de veces que pase por el color $1$ y $3$ (ver figura) entonces en todo momento del recorrido se cumple que $|A-B|\leq 2$.
Pero como hay $n>2$ casillas de color $1$ que de color $3$ sucede que no podemos recorrer todo el tablero ya que si lo hicieramos sucedería que $|A-B|=n$, contradicción.

SIbero2006P1.png