La profesora Junio posee un tablero de ajedrez de 99 × 99, cuyas filas están numeradas consecutivamente del 1 al 99 y cuyas columnas también están numeradas consecutivamente del 1 al 99.
Un caballo inusual puede saltar de una casilla en la columna n-ésima a cualquier casilla en la fila n-ésima ( y no puede saltar a ninguna otra casilla); ten en cuenta que si el caballo puede saltar del cuadrado x al cuadrado y, esto no significa que también pueda saltar del cuadrado y al cuadrado x.
La profesora afirma que existe un recorrido cerrado en el tablero de ajedrez que hace que el caballo visite cada casilla exactamente una vez, y al final lo lleva de vuelta a su casilla inicial.
Pregunta: ¿Es cierto lo que dice Junio o nos quiere tomar el pelo?
Y si es verdad, indica esa ruta.
Por lo pronto si el lado del cuadrado es un número primo el problema siempre tiene solución. 99 no es un número primo, pero no por eso lo descartaría. El 4 no es primo y sin embargo sé que existe solución para un cuadrado de 4×4 casillas. Puede ser que sean todos solubles, hasta donde yo sé. No he encontrado contraejemplos, aunque no he buscado con tanto detenimiento.
Yo tampoco he encontrado contraejemplos de momento.
He comprobado que se puede conseguir para tableros 3×3 y 5×5 (por probar con los impares)
Como curiosidad, este juego con tablero 7×7 sería exactamente lo mismo que el dominó (es decir, si se pueden colocar todas las fichas del dominó siguiendo las reglas del juego sin que sobre ninguna, entonces también se podrá hacer que el caballo visite cada casilla exactamente una vez en el tablero 7×7)
Sería interesante ver qué pasa en el tablero 9×9 (por ser impar pero no primo)
Creo que Show ▼
A ver si consigo explicarlo:
Show ▼
Show ▼
Aclaración:
Cuando escribo n,m (o simplemente nm) esto significa fila-n columna-m.
Fe de erratas:
He puesto varias veces «hai» en lugar de «hay». Es el corrector del móbil, que está en gallego y siempre me hace este tipo de jugadas cuando escribo en castellano. Lo digo por si a alguien le estaban sangrando los ojos, que no se asuste.
Yo lo planteo por la diferencia de coordenadas (columna – fila) pero siempre positivo: (1,3) tiene una diferencia de 2 y (3,1) tiene una diferencia de 97 en una cuadrícula de 99: para ir del 3 al 1 tengo que avanzar 97 casillas. Lo generalizo para un cuadrado de nxn, que siempre tiene solución.
Voy a hacer bucles cerrados que se puedan unir después entre ellos. Por ejemplo, si tengo un bucle (1,5) (5,3) (3,1) y otro (3,6) (6,7) (7,3) los puedo unir si tienen un elemento en común, en este caso el 3, así: (1,5) (5,3) (3,6) (6,7) (7,3) (3,1). Tengo que conseguir al menos un bucle cerrado que tenga todos los números, para después poder unirle todos los demás, y garantizar que utilizo todos los puntos de paso.
Lo primero lo consigo con un bucle especial, que usaré como base, que tiene todos los puntos cuya diferencia es 0 o 1: (1,1) (1,2) (2,2) (2,3) (3,3) … (n-1,n-1) (n-1,n) (n,n) (n,1). Es cerrado porque a continuación puedo volver al (1,1).
Ahora hago bucles con todos los puntos con la misma diferencia de coordenadas. En el caso de 2 obtengo para la cuadrícula de 99×99 (1,3) (3,5) (5,7) … (97,99) (99,2) (2,4) … (96,98) (98,1). Pueden pasar dos cosas dependiendo de si la diferencia (2) y el lado de la cuadrícula (99) son coprimos o no. Si son coprimos se forma un único bucle, si no lo son se va a formar un número de bucles cerrados que el máximo común divisor de los dos números (por eso es 1 cuando son coprimos). En cualquier caso tenemos bucles cerrados. Por ejemplo, para el caso de lado 99 y diferencia 3 tengo los bucles (1,4) (4,7) … (94,97) (97,1), (2,5) (5,8) … (95,98) (98,2) y (3,6) (6,9) … (96,99) (99,1).
La única diferencia que no genera bucles cerrados es 0, pero esos puntos los usé todos en el primer bucle, así que tengo todos los números en los bucles.
He usado todos los números en bucles cerrados y hay un bucle que sé que conecta todos los números. Ahora uno todos los bucles en uno y ya está la solución.