Voy a escribir acá más o menos el proceso por el que pasé recién resolviendo el problema.
Por qué? Yo soy experto en quemarme problemas, a veces tengo ganas de ver alguna solución elegante sin pensar mucho un problema sólo por interés. Y si bien creo que ver una solución me deja conocer a veces alguna herramienta que no tenía presente, muchas veces me veo pensando "dah ni en pedo se me ocurre eso". Creo que si viera el proceso por el cual esa persona o grupo de personas llegó a esa solución, me sentiría más cerca a pensar que se me podría haber ocurrido algo de ese estilo.
No quiero dejar como enseñanza quemarse problemas, de hecho por esta razón creo que no sirve mucho al proceso de aprendizaje a interiorización de conceptos. Sólo digo que a veces lo hago demasiado rápido
Entonces para que esto no se convierta en un Instagram cualquiera donde la gente pone sólo cosas lindas sin mostrar frustraciones (?), voy a dejar expresado mi proceso con las vueltas que di. Por eso es que este texto, para mucha gente, sobre todo si quieren ir directo a la solución, va a ser súper vueltero. Imagínense todo lo que escribí hasta acá y ni empecé con la solución.
Mi idea era hacer esto para gente que va avanzando y quiere ver si alguien más estaba en su camino, o si se traban en alguna parte que describo acá poder destrabarse entendiendo cómo yo llegué a poder hacerlo. O si después de pensarlo un rato quieren una solución que intenta no sacar nada de la galera tipo esos "Lema: El problema es equivalente a pensar en un tetraedro donde reemplazamos a cada número $x$ por $2^x$ ", que cada vez que encuentro cosas así me molesta un poco.
También escribo porque hacía bastante no pensaba un problema tanto tiempo seguido sin programar nada en el medio, y tenía ganas de postear lo que pensé
Durante el problema si digo primera fila me refiero a la de abajo de todo, última fila es la de arriba. De la misma manera la primera columna será la de la izquierda y la última la de la derecha.
Cuando $n = 1$ la cantidad de pasos es $0$, así que asumo $n > 1$.
Aclaración que no explico después: La menor cantidad de pasos para ir de una casilla a la otra, como sólo se puede pasar por vecinas, es la diferencia de las filas de ambas casillas más la diferencia de las columnas de ambas casillas.
Menor valor de $N$ (me salió más fácil que el mayor valor):
- Spoiler: mostrar
- Empecé pensando que me convenía que los números consecutivos estuvieran pegados, para no tener que hacer muchos movimientos.
Entonces, como escuché alguna vez (https://www.youtube.com/watch?v=mqWPS9LkFvo#t=52s), pensé casos chicos:
$$\begin{array}{|c|c|}\hline
\quad 2 & \quad 3 \\
\hline
\quad 1 & \quad 4 \\
\hline
\end{array}$$
Este caso da como respuesta $4$ movimientos.
$$\begin{array}{|c|c|c|}\hline
\quad 3 & \quad 4 & \quad 7 \\
\hline
\quad 2 & \quad 5 & \quad 6 \\
\hline
\quad 1 & \quad 9 & \quad 8 \\
\hline
\end{array}$$
Este caso da como respuesta $10$ movimientos.
$$\begin{array}{|c|c|c|c|}\hline
\quad 4 & \quad 5 & \quad 10 & \quad 11 \\
\hline
\quad 3 & \quad 6 & \quad 9 & \quad 12 \\
\hline
\quad 2 & \quad 7 & \quad 8 & \quad 13 \\
\hline
\quad 1 & \quad 16 & \quad 15 & \quad 14 \\
\hline
\end{array}$$
Este caso da como respuesta $16$ movimientos.
Estos casos me dieron la siguiente idea: Cuando $n$ es par, puedo formar el espiral como se ve acá y lograr el objetivo en $n^2$ movimientos, que claramente es el mínimo ya que debo llevar la casilla a $n^2$ lugares distintos y la distancia entre dos lugares distintos es al menos $1$.
Ahora, cuando $n$ es impar, no estoy pudiendo. Será que no estoy encontrando la manera, o realmente no se puede en $n^2$ movimientos?
Primero vi el caso $n=5$:
$$\begin{array}{|c|c|c|c|c|}\hline
\quad 5 & \quad 6 & \quad 9 & \quad 10 & \quad 13 \\
\hline
\quad 4 & \quad 7 & \quad 8 & \quad 11 & \quad 12 \\
\hline
\quad 3 & \quad 17 & \quad 16 & \quad 15 & \quad 14 \\
\hline
\quad 2 & \quad 18 & \quad 19 & \quad 20 & \quad 21 \\
\hline
\quad 1 & \quad 25 & \quad 24 & \quad 23 & \quad 22 \\
\hline
\end{array}$$
En este caso cumplo el objetivo con $26$ movimientos.
Aparentemente, haciendo este espiral, siempre puedo lograr el objetivo en $n^2+1$ pasos.
Veamos que es así: Arranco con el $1$ abajo a la izquierda. Subo, me muevo para la derecha. Y desde ahí, zigzagueo en las dos primeras filas hasta llegar a la casilla de arriba a la derecha, ya que en la segunda columna bajo, en la tercera subo, y así en todas las impares subo, hasta la enésima que es impar, y entonces termino subiendo.
Desde ahí, como la casilla abajo de esta ya fue visitada, bajo $2$ casillas y pongo el siguiente número, y ahora empiezo a zigzaguear cubriendo filas completas: Voy todo hacia la izquierda hasta la segunda columna, bajo, voy hacia la derecha, bajo. Y así, en las filas impares voy hacia la izquierda, terminando en la primera fila yendo hacia la izquierda, y colocando el número $n^2$ al lado del $1$.
Veamos que siempre que voy a una casilla sin visitar y agrego el siguiente número, vengo desde una casilla automáticamente vecina, excepto cuando bajo $2$ casillas desde arriba a la derecha. Luego, la cantidad de movimientos es $n^2+1$.
Ahora, lo que tengo que hacer es demostrar que con $n^2$ pasos no se puede, y como con menos tampoco se puede, estaremos hechos con el procedimiento de $n^2+1$.
Y ahora recurrí a una idea que se usa en muchos problemas sobre todo cuando hay tableros y movimientos que es el de pintar las casillas. Pintemos las casillas como un tablero de ajedrez o damas, alternando el blanco y el negro de manera que no haya dos casillas consecutivas del mismo color.
Entonces, si quiero lograr el objetivo en $n^2$ pasos, debo siempre encontrar la siguiente casilla del camino, al lado de donde estoy parado. Luego, la siguiente casilla tendrá un color distinto a la actual.
Ahora, como $n$ es impar, la cantidad de casillas $n^2$ también es impar, por lo que habrá, por ejemplo, una casilla negra más que casillas blancas.
Si empiezo desde una casilla negra, por más que intente no tener dos consecutivas del mismo color no puedo, ya que el procedimiento debería ser $N - B - N - B - N - B ... - N - B - N$, pero luego al ir de la última $N$ a la primera deberé hacer al menos dos movidas ya que si estuvieran consecutivas serían de distinto color. Y si empiezo en una blanca, haría Blanca - Negra - Blanca - Negra ... hasta quedarme sin Blancas pero necesitando cubrir una más que será una Negra e irá luego de otra Negra, teniendo ahí que hacer al menos dos movimientos.
Entonces, cuando $n$ es impar, no puedo cumplir el objetivo con $n^2$ pasos o menos, pero siempre puedo con $n^2+1$, con el procedimiento más arriba.
Y cuando $n$ es par vimos que se puede con $n^2$ pasos, haciendo como en el ejemplo con $n=4$: Voy desde abajo a la izquierda, subo hasta la última fila, me muevo hacia la derecha, bajo hasta la segunda fila, y así voy zigzagueando subiendo hasta arriba de todo y bajando hasta la segunda fila, hasta llegar a la última columna y segunda fila (ya que en las columnas pares bajo y $n$ es par), y ahí bajo una casilla más y voy todo hacia la izquierda.
Mayor valor de $N$:
- Spoiler: mostrar
-
Para esta parte empecé con casos chicos, ubicando los números empezando abajo a la izquierda y yendo a la casilla más alejada posible (o una de las si hay varias):
$$\begin{array}{|c|c|}\hline
\quad 3 & \quad 2 \\
\hline
\quad 1 & \quad 4 \\
\hline
\end{array}$$
Este caso da como respuesta $6$ movimientos.
$$\begin{array}{|c|c|c|}\hline
\quad 4 & \quad 8 & \quad 2 \\
\hline
\quad 6 & \quad 9 & \quad 7 \\
\hline
\quad 1 & \quad 3 & \quad 5 \\
\hline
\end{array}$$
Este caso da como respuesta $24$ movimientos.
$$\begin{array}{|c|c|c|c|}\hline
\quad 7 & \quad 9 & \quad 12 & \quad 2 \\
\hline
\quad 11 & \quad 16 & \quad 14 & \quad 4 \\
\hline
\quad 5 & \quad 13 & \quad 15 & \quad 10 \\
\hline
\quad 1 & \quad 3 & \quad 8 & \quad 6 \\
\hline
\end{array}$$
Este caso da como respuesta $60$ movimientos.
Spoiler que me llevó mucho tiempo (pueden seguir sin leerlo): - Spoiler: mostrar
- $60$ no es el mejor caso para $n = 4$
Entonces, viendo estos números, dije "uh qué lindo, cuando $n = 2$ la respuesta es $6 = 6 \cdot 1$, cuando $n = 3$ la respuesta es $24 = 6 \cdot 4$, cuando $n = 4$ la respuesta es $60 = 6 \cdot 10$... qué pasará que son todos múltiplos de $6$?
Y después pensé, "bancá, no tiene mucho sentido que el $6$ sea importante, a ver si puedo encontrar otro patrón" y encontré:
$n = 2, N = 2 \cdot 3$
$n = 3, N = 3 \cdot 8$
$n = 4, N = 4 \cdot 15$
Okey, parecería que $N = n \cdot (n^2 - 1)$.
También, como la distancia máxima entre dos casillas (dos esquinas) es $2 \cdot (n-1)$, intenté meter este número y pude, $N = (2 \cdot (n-1)) \cdot \dfrac{n \cdot (n+1)}{2} $ (que tiene sentido pues $(n-1) \cdot (n+1) = (n^2 - 1)$ ) . Y qué lindo cuando aparece $\dfrac{n \cdot (n+1)}{2}$ de la nada.
Con esas fórmulas en mente, intenté ver si había algo en el procedimiento que había hecho que le diera forma a alguna de ellas. Por ejemplo, buscar una cota pensando que en cada paso me muevo $2 \cdot (n-1)$ veces, que es el máximo.
Pero no encontré nada, sobre todo porque el procedimiento no estaba muy bien descripto, era simplemente "me muevo a la más alejada", sin ningún registro de qué casillas ya visité ni nada.
Primero pensé por un rato "bueno, quiero demostrar que si voy siempre a la más alejada es lo mejor que puedo hacer", y ahí intenté ver que hacer $1 - 2 - 3 - 4$ era más corto que $1 - 3 - 2 - 4$ siempre que la distancia entre $1$ y $2$ fuera más corta que entre $1$ y $3$. Pero eso no tenía sentido, dado que si digo que el primer caso es peor que el segundo sin ver las distancias con la casilla $4$, entonces si veo el camino invertido (empezando en la $4$ hasta la $1$), ahora no estoy mirando la primera distancia, que es lo que dije antes que definía cuál movida era mejor.
Después de un poco de esto, se me ocurrió pensar qué pasa cuando voy a otra casilla? Sumo a la distancia, la diferencia entre las filas y la diferencia entre las columnas. Pensemos en una dimensión primero, las filas. Si voy de la fila $f_1$ a la $f_2$ con $f_1 < f_2$, a la distancia le sumo $f_2 - f_1$. Y si voy para abajo, es decir de $f_2$ a $f_1$, también sumo $f_2 - f_1$.
Entonces en un movimiento, siempre sumo el valor de la fila más grande y resto el de la fila más chica. Y acá estuvo la clave. Ahora quiero ordenar las filas de manera de sumar lo máximo posible y restar lo mínimo posible. Por ejemplo, mirando las filas, siempre quiero ir de la fila $1$ a la $n$ y de la $n$ a la $1$, el tema es que en cada fila tiene $n$ filas. Pero bueno, si puedo sumar todas las de $n$, restar las de $1$, sumar las de $n-1$, restar las de $2$, y así sucesivamente, voy a obtener el camino más largo.
Volviendo un poco al tablero, voy a intentar zigzaguear lo más lejos posible entre dos casillas de números consecutivos. Por ejemplo, si voy de la fila $7$ a la $1$ y de ahí a la $6$, sumo en total $6 + 5 = 11$ movimientos. Mientras que si voy de la $7$ a la $6$ y de ahí a la $1$, sumo $1 + 5 = 6$, que es menos. La diferencia es que primero hago $(7-1) + (6-1)$ y en el otro caso $(7-6) + (6-1)$.
Como tenemos que ubicar los números en todas las casillas, sabemos que a todas las casillas deberemos "entrar" como parte del camino, y luego salir. (Podemos pasar varias veces por varias casillas en el medio pero el camino será el conjunto de $n^2$ casillas ordenadas que contienen números consecutivos.)
Por ejemplo, si $n = 4$, me gustaría, mirando filas, hacer $1 - 4 - 1 - 4 - 2 - 3 - 2 - 3$. De esta manera, sé que sumo lo máximo posible ya que los números $1$ y $2$ están entre números $3$ y $4$, por lo que los $1$ y $2$ siempre restan (ya que son menores a sus vecinos) y los $3$ y $4$ siempre suman.
Ahora que vimos esto, el desafío está en agregar la otra dimensión. Porque puede ser que queriendo hacer este zigzag entre números chicos y grandes de filas nos quedemos sin poder alternar también columnas.
Ahora, voy a "pintar" el tablero pero de una manera más rara que en la primera parte del problema. Muestro ejemplo para $n=4$ que generaliza los casos cuando $n$ es par, los casos de $n$ impar los veremos después:
$$\begin{array}{|c|c|c|c|}\hline
\quad 3 & \quad 3 & \quad 4 & \quad 4 \\
\hline
\quad 3 & \quad 3 & \quad 4 & \quad 4 \\
\hline
\quad 1 & \quad 1 & \quad 2 & \quad 2 \\
\hline
\quad 1 & \quad 1 & \quad 2 & \quad 2 \\
\hline
\end{array}$$
Es decir, divido a las casillas en $4$ grupos: fila de valor chico Y columna de valor chico (1), fila de valor chico Y columna de valor grande (2), fila de valor grande Y columna de valor chico (3), fila de valor grande Y columna de valor grande (4).
Ahora, por lo que dije antes, a mí me gustaría ir del grupo $1$ al grupo $4$, del $2$ al $3$, del $3$ al $2$ y del $4$ al $1$.
Como se puede ver, cuando $n$ es par, no voy a poder: Podría alternar entre grupo $1$ y $4$ primero pero al agotar esas casillas tendré que ir del grupo $4$ al $3$ ó al $2$, restando así una fila de valor grande ó una columna de valor grande respectivamente.
Acá es cuando encontré un ejemplo con $n = 4$ mejor al que tenía, en el cual uso esta estrategia de los grupos y después intento no restar "tanto", restando como fila grande la fila $3$ (sería peor restar la fila $4$) y sumando como fila chica la fila $2$ (sería peor sumar la fila $1$):
$$\begin{array}{|c|c|c|c|}\hline
\quad 13 & \quad 15 & \quad 4 & \quad 8 \\
\hline
\quad 11 & \quad 9 & \quad 2 & \quad 6 \\
\hline
\quad 3 & \quad 7 & \quad 14 & \quad 16 \\
\hline
\quad 1 & \quad 5 & \quad 12 & \quad 10 \\
\hline
\end{array}$$
Este ejemplo da un camino de $62$ pasos en vez de $60$ como tenía antes. Ahora ya descarté las fórmulas que tenía antes pero encontré la estrategia de pintar que pinta más prometedora. Se puede ver que con esta estrategia es muy fácil encontrar distintos caminos que cumplan con la misma cantidad total de movimientos.
De hecho, se puede por qué antes el ejemplo nos dio más bajo: En los movimientos $5 \rightarrow 6, 11 \rightarrow 12, 14 \rightarrow 15, 16 \rightarrow 1$, estamos haciendo movimientos donde, respectivamente, la fila más grande tiene valor $2$, la columna más chica tiene valor $3$, la fila más chica tiene valor $3$ y la columna más grande tiene valor $2$. Entonces, viendo estos "errores", entendemos por qué la suma da $60$ en vez de $62$.
Intentemos formalizar un poco esto de filas y columnas grandes y chicas.
Supongamos que tengo un camino de casillas: $c_1, c_2, c_3, ..., c_{n^2}$, en donde $c_i$ tiene el número $i$ escrito, es decir, están en el orden en el que las tengo que recorrer.
Cuál va a ser la distancia?
Si digo que la casilla $c_i$ está en la fila $x_i$ y columna $y_i$, entonces pienso al camino de casillas como $(x_1, y_1), (x_2, y_2), (x_3, y_3), ..., (x_{n^2}, y_{n^2})$, y la distancia total será $|(x_1 - x_2)| + |(y_1 - y_2)| + |(x_2 - x_3)| + |(y_2 - y_3)| ... $, entonces, acá podemos apreciar que $x_2$, $y_2$ aparecen en dos términos, con la casilla $1$ y la $3$. Esto mismo pasa con todas las casillas, dado que al final volvemos a la primera. Ahora, qué valores toman por ejemplo las filas, $x_1, x_2, ...$? Son las filas de todas las casillas! Entonces entre los valores $x_1, x_2, ..., x_{n^2}$ tendremos $n$ veces el $1$, $n$ veces el $2$, y así siguiendo, $n$ veces cada número del $1$ al $n$ dado que cada fila tiene $n$ casillas.
Entonces, podemos definir un camino (en filas) como una asociación de signos $+$ y $-$, donde repartimos la misma cantidad de cada uno, a $2n$ números $1$, $2n$ números $2$, etc.
Si repartiéramos así los números, cuánto nos daría la distancia en filas:
(Por ahora sigo viendo los casos donde $n$ es par)
Asignamos los $+$ a las casillas de las filas $n, n-1, ..., n/2+1$ y los $-$ a las casillas de las fillas $1, 2, ..., n/2$.
Luego, la suma quedaría $ S = 2n \cdot (n+(n-1)+...+(n/2+1) - 1 - 2 ... - n/2)$, donde podemos pensar a la suma del paréntesis como la suma desde $1$ hasta $n$ restando dos veces la suma desde $1$ hasta $n/2$: $$S = 2n \cdot (\dfrac{n \cdot (n+1)}{2} - 2 \cdot \dfrac{n/2 \cdot (n/2+1)}{2}) = n^2 \cdot (n+1 - (n/2+1)) = \dfrac{n^3}{2}$$ .
Ahora bien, esta suma es para la distancia vertical, entre filas. Para la distancia horizontal la cuenta será la misma, obteniendo como cota máxima $n^3$.
Pintando el tablero como vimos antes, de a grupos, es imposible que el camino conste como dijimos de filas de valor grande entre filas de valor chico y viceversa a la vez que columnas de valor grande entre columnas de valor chico y viceversa.
Luego, deberemos intercambiar al menos un signo $+$ con un signo $-$ en nuestro camino. Como los valores que tenían signos $+$ son todos distintos de los que tienen signo $-$, deberemos elegir al menos dos valores de diferencia $1$, por lo que a la suma total de $n^3$ le restaremos al menos $2$.
Siguiendo el ejemplo óptimo mencionado con $n=4$, podemos armar un camino que vaya desde casillas del grupo $1$ a casillas del grupo $4$ y vuelvan, dejando una casilla del grupo $4$ de la fila de arriba de todo para terminar, y yendo luego a una casilla del grupo $3$ de la fila más baja posible (es decir de valor $n/2+1$), y luego alternando entre casillas del grupo $2$ y $3$, dejando como última casilla del grupo $2$ una de la fila $n/2$, y luego yendo a la casilla inicial, obteniendo así el valor deseado de $n^3-2$.
Y qué pasa cuando $n$ es impar?
Ahora, al ir asignando signos $+$ a la fila $n$, $-$ a la fila $1$, $+$ a la fila $n-1$, etcétera, llegamos a asignar $+$ a la fila $(n+1)/2+1$ y signos $-$ a la fila $(n+1)/2-1$, quedando sin asignar la fila de valor $(n+1)/2$. Pero recordemos que en esta asignación tenemos $2n$ números de cada valor, dado que en la suma total de distancia los valores aparecen con la casilla previa y la siguiente. Entonces, a los $2n$ números de valor $(n+1)/2$ simplemente les asignaremos signos $+$ a la mitad y signos $-$ a la otra mitad.
Entonces, podemos pintar el tablero así (ejemplo cuando $n=5$ que generaliza cuando $n$ es impar):
$$\begin{array}{|c|c|c|c|c|}\hline
\quad 3 & \quad 3 & \quad 7 & \quad 4 & \quad 4 \\
\hline
\quad 3 & \quad 3 & \quad 7 & \quad 4 & \quad 4 \\
\hline
\quad 5 & \quad 5 & \quad 0 & \quad 6 & \quad 6 \\
\hline
\quad 1 & \quad 1 & \quad 8 & \quad 2 & \quad 2 \\
\hline
\quad 1 & \quad 1 & \quad 8 & \quad 2 & \quad 2 \\
\hline
\end{array}$$
Ahora el grupo $5$ son las de columna chica y fila central, el grupo $6$ son las de columna grande y fila central, el grupo $7$ son las de fila grande y columna central y el grupo $8$ son las de fila chica y columna central. La casilla $0$ es la central del tablero.
Luego, para sumar lo máximo posible debemos poner un casilla de fila chica o central entre dos de filas grandes o centrales, y viceversa, y lo mismo para los valores de las columnas.
Gracias a estos nuevos grupos no tendremos que ir del grupo $4$ al $3$ por ejemplo, como sí necesitábamos cuando $n$ era par. Podemos simplemente ir del $1$ al $4$, cuando agotamos todas estas casillas vamos de la última del grupo $4$ a una del grupo $5$, luego alternar entre grupos $5$ y $6$ logrando maximizar sumas de columnas usando algunos $+$ y $-$ de la fila central; al agotar estas casillas ir a alguna del grupo $3$, alternar entre grupo $3$ y $1$, luego ir de la última del grupo $1$ al grupo $7$ y ahí alternar entre grupos $7$ y $8$ para maximizar suma de filas, y terminar yendo a la casilla central.
Un ejemplo podría ser:
$$\begin{array}{|c|c|c|c|c|}\hline
\quad 15 & \quad 17 & \quad 23 & \quad 4 & \quad 8 \\
\hline
\quad 13 & \quad 19 & \quad 21 & \quad 2 & \quad 6 \\
\hline
\quad 11 & \quad 9 & \quad 25 & \quad 12 & \quad 10 \\
\hline
\quad 3 & \quad 7 & \quad 22 & \quad 14 & \quad 16 \\
\hline
\quad 1 & \quad 5 & \quad 24 & \quad 18 & \quad 20 \\
\hline
\end{array}$$
En este ejemplo, la cantidad de pasos total es $120$.
Y veamos la fórmula para el máximo valor de $N$ cuando $n$ es impar:
$$
S_{filas} = 2n \cdot (n+(n-1)+...+((n+1)/2+1) - 1 - 2 ... - ((n+1)/2-1) ) =
$$
$$
2n \cdot (\dfrac{n \cdot (n+1)}{2} - (n+1)/2 - 2 \cdot \dfrac{((n+1)/2-1) \cdot (n+1)/2}{2})
$$
Acá hice el mismo truco de antes de hacer la suma desde $1$ a $n$ y restar dos veces la suma de $1$ a $(n+1)/2-1$ pero con el cuidado de también sacarle $(n+1)/2$ ya que no aparece en la cuenta original y lo estaba contando al sumar todos del $1$ al $n$.
$$
S_{filas} = n \cdot (n \cdot (n+1) - (n+1) - ((n+1)/2-1) \cdot (n+1)) =
$$
$$n \cdot (n+1) \cdot (n - 1 - ((n+1)/2-1)) = n \cdot (n+1) \cdot (n - (n+1)/2)
$$
Luego, la suma total será el doble de esto, $S = n \cdot (n+1) \cdot (n-1)$ como sospeché al principio, pero sólo en los casos impares.
