Solución: 101 castillos de arena

Publicamos la solución al divertimento 101 castillos de arena. Hemos recibido respuestas correctas de Magdalena Jáñez Vaz, Renato Álvarez y Niurka Rodríguez, Don Pablo y Don Diedro, anónimo17 y Ángel Yáñez Vaz.

Divertimento:

Un padre ha hecho una fila de 101 castillos de arena en la playa, alineados y separados cada uno del siguiente por una distancia de un metro. Sus hijos, que están deseosos de romperlos, pueden empezar por un extremo y acabar en el extremo opuesto, rompiendo los castillos de uno en uno y sin cambiar de dirección; de esta forma consiguen romper los castillos recorriendo la menor distancia posible. Pero el padre, que se ha llevado un libro a la playa, les plantea algo un poco más difícil: ¿en qué orden habría que romper los castillos para que la distancia recorrida sea la mayor posible? ¿Cuál es esa distancia?

Por ejemplo, en el caso de tres castillos A, B y C, dispuestos en ese orden, se recorren 2 metros si se rompen en el orden ABC, y se recorren 3 metros si se rompen en el orden ACB o BAC, y no hay forma de recorrer más distancia.

Solución:

Vamos a comenzar considerando una cantidad arbitraria de castillos.

Fijamos el origen de coordenadas en el castillo que está en uno de los extremos, de modo que las coordenadas de los castillos son los números de \(0\) a \(n\). Con esta notación hay \(n+1\) castillos. Podemos denotar cada trayectoria mediante una permutación de los números \(\{0,1, \ldots ,n\}\), indicando las coordenadas del castillo que rompemos. Por ejemplo, \((0,1,2, \ldots, n)\) se corresponde con el caso en que se comienza por un extremo y se acaba en el otro.

Comenzamos observando que, si \((x_0,x_1,\ldots,x_n)\) es una trayectoria en la que el castillo \(x_i\) está entre \(x_{i-1}\) y \(x{i+1}\) para algún valor de \(i\), entonces la trayectoria \((x_0,x_1, x_{i-1},x_{i+1},\ldots ,x_n,x_i)\) es más larga que \((x_0,x_1,\ldots,x_n)\). Por tanto, la trayectoria más larga se obtiene necesariamente cambiando de dirección después de romper cada castillo, y cumple que
$$
x_0<x_1, \qquad x_1 > x_2, \qquad x_2 < x_3, \qquad x_3 > x_4 \ldots
$$
El caso \(x_0 > x_1\) es simétrico y se obtiene invirtiendo los sentidos de todas las desigualdades.

Si el número de castillos es impar, entonces se recorre una cantidad par de trayectorias entre dos castillos. Como cada vez se cambia de sentido, el trayecto entre los dos últimos castillos tiene el sentido opuesto al trayecto entre los dos primeros, y la distancia que se recorre es
$$
d_1=(x_1-x_0)+(x_1-x_2)+(x_3-x_2)+(x_3-x_4)+ \ldots + (x_{n-1}-x_n)
$$
Se tiene entonces que
\begin{align*}
d_1 & = (x_1-x_0)+(x_1-x_2)+(x_3-x_2)+(x_3-x_4)+ \ldots + (x_{n-1}-x_{n}) \\
& = 2(x_1+x_3+x_5 + \ldots + x_{n-1}) -2(x_2+x_4+ \ldots +x_{n-2}) – (x_0+x_n) \\
& = 2(x_0+x_1+x_2 + \ldots + x_{n}) -4(x_2+x_4+ \ldots +x_{n-2}) – 3(x_0+x_n) \\
& = n(n-1) -4(x_2+x_4+ \ldots +x_{n-2}) – 3(x_0+x_n)
\end{align*}
Esta cantidad alcanza su mayor valor para
$$\{x_2,x_4, \ldots ,x_{n-2}\} = \left\{0,1,…,\frac{n-4}{2}\right\}$$ y
$$\{x_0,x_n\} = \left\{\frac{n-2}{2}, \frac{n}{2}\right\},$$ lo que fuerza que
$$\{x_1,x_3, \ldots ,x_{n-1}\}=\left\{\frac{n+2}{2},\ldots,n\right\}$$ Cualquier trayectoria que cumpla esta condición tiene distancia máxima. Además esta distancia es igual a
$$
d_1 = n(n-1) – 4 \frac{\frac{n-4}{2}\left( \frac{n-4}{2} + 1\right)}{2} – 3 \left( \frac{n-2}{2} + \frac{n}{2} \right) = \frac{n^2+2n-2}{2}
$$
En nuestro caso tenemos que \(n=100\) y que dicha distancia es igual a 5099 metros.

Si algún lector del blog se ha quedado con ganas de romper más castillos, puede comprobar que si el número de castillos es par la distancia que se recorre es
$$
d_2=(x_1-x_0)+(x_1-x_2)+(x_3-x_2)+(x_3-x_4)+ \ldots + (x_{n}-x_{n-1}),
$$
y se tiene que
\begin{align*}
d_2 & = (x_1-x_0)+(x_1-x_2)+(x_3-x_2)+(x_3-x_4)+ \ldots + (x_{n}-x_{n-1}) \\
& = n(n+1) -4(x_2+x_4+ \ldots +x_{n-1}) – (3x_0+x_n).
\end{align*}
El mayor valor de esta expresión se alcanza cuando
$$\{x_2,x_4, \ldots ,x_{n-1}\}=\left\{0,1,2, \ldots, \frac{n-1}{3}\right\}$$
$$\{x_1,x_3, \ldots ,x_{n-2}\}=\left\{ \frac{n+3}{2}, \frac{n+5}{2}, \ldots n \right\}$$
$$x_0=\frac{n-1}{2}, \qquad x_n=\frac{n+1}{2},$$
y es igual a
$$
d_2=n(n+1)-4 \frac{\frac{n-3}{2}\left(\frac{n-3}{2} + 1\right)}{2}-\left( 3 \frac{n-1}{2} + \frac{n+1}{2} \right) = \frac{n^2+2n-1}{2}
$$