Nacional 2012 P6 N2

[Matías V5]

Se tienen [math]2k fichas ubicadas en una fila. Una movida consiste en intercambiar dos fichas vecinas. Se deben realizar varias movidas de modo que cada ficha visite la primera y la última posición. ¿Cuál es el menor número de movidas necesarias para lograr esto?

[Fran5]

Yo me acuerdo que en este problema me había dado una solución re flashera xD
Aunqe no me acuerde como lo hice exactamente, era algo asi

Spoiler: mostrar

Para simplificar un poco las cosas, numero a cada ficha según la posición que ocupe, es decir, las numero [math]1, 2, 3, ... 2k
Y por las dudas, a cada movida la llamo enroque (como en el ajedrez)

Algo que es interesante notar acá es el orden en el que llegan las fichas a la primer y la última posición
En la primer posición aparece primero [math]1, luego [math]2, luego[math]3 , así hasta [math]k-1, y luego aparece [math]2k, luego [math]2k-1, asi hasta que aparece [math]k+1
Y de forma inversa para la última posición.
En efecto, el camino más corto para la ficha [math]j con [math]1\leq j \leq k, es ir primero hacia la primera posición, y luego hacia la última posición.
Análogamente, para [math]j' con [math]k+1 \leq j' \leq 2k, es más corto ir primero hacia la última posición y luego hacia la primera posición.
Siguiendo esta lógica, cada ficha debe viajar hacia las extremidades de la fila, y reubicarse dentro de ella para dejar paso a las demás fichas y no usarse en futuros movimientos innecesarios (1)

Al principio estarán en esta disposición
[math](1)|(2)|(3)|...|(k-1)|(k)||(k+1)|(k+2)|...|(2k-1)|(2k)

Y luego de que cada ficha visite la primer o última posición, estarán así
[math](k+1)|(k+2)|...|(2k-1)|(2k)||(1)|(2)|...|(k-1)|(k)

Veamos como se hace (?

Cada una de las fichas va la primera posición (si es menor o igual a [math]k) o va a la última posición (si es mayor o igual a [math]k+1)

Llamaremos movida al conjunto de [math]2k-1 movimientos que se dan de la siguiente forma
Usaremos la simetría de la fila
Se enrocan [math]1 y [math]2, luego [math]1 y [math]3, así hasta llegar al enroque de [math]1 y [math]k
Luego, se enrocan [math]1 y [math]2k
Se ve que hubo [math]2(k-1)+1=2k-1 movimientos

Por lo visto arriba, es necesario que primero las [math]2k fichas alcancen la punta más cercana
Entonces, necesitamos [math]k-1 movidas
Sumada a una última que implica llevar el [math]1 y el [math]2k a la punta opuesta

En total se usaron [math](k-1)(2k-1)+(2k-1)=k(2k-1)

Y la disposición del tablero termina quedando invertida, es decir

[math](2k)|(2k-1)|(2k-2)|...|(3)|(2)|(1)

Ahora, es necesario llevar los elementos de las puntas hacia el centro
De nuevo usamos la simetría de la fila
Primero hacemos enroque entre [math]1 y [math]2, luego entre [math]1 y [math]3, hasta [math]1 y [math]k
Entonces hemos hecho [math]2(k-1) movimientos
Luego, hacemos enroque entre [math]2 y [math]3, luego entre [math]2 y [math]4, hasta [math]2 y [math]k
Entonces hemos hecho [math]2(k-2) movimientos
Seguimos así hasta hacer enroque entre [math]k-1 y [math]k que implica [math]2 movimientos

En total se usaron [math]2(k-1)+2(k-2)+...+4+2=2(\frac{k(k-1)}{2})=k(k-1)

Sumando los movimientos totales queda que en total se usan
[math]k(2k-1)+k(k-1)=2k^2-k+k^2-k=3k^2-2k movimientos

Que por lo demostrado en (1) es la menor cantidad

[Melanie]

Voy a explicar un poco mejor la cota que da Fran5, porque no está desarrollada dentro de la solución (el ejemplo sí está explicado).

Queremos ver que se necesitan al menos [math]3k^2-2k movimientos para lograr lo pedido, y para ello contaremos la cantidad de movimientos mínima de cada ficha por separado. Luego, vamos a haber estado contando dos veces cada movimiento (una vez por cada ficha involucrada) por lo que deberemos dividir por 2 el resultado que obtengamos.

El movimiento de una ficha que inicialmente está en el lugar [math]j se puede resumir como:

• Ir desde [math]j a un borde para visitar uno de ellos.
• Ir desde ese borde al otro borde para recorrer todas las posiciones que faltan.
• Ir desde el otro borde a la posición final de la ficha.

Tenemos que dar una cota inferior, así que si bien puede hacer más movimientos daremos la mínima cantidad. Primero sumaremos las dos primeras secciones de la enumeración, y luego contaremos la tercera. Para este análisis, separemos [math]j en dos casos según su posición inicial.

Si [math]1 \leq j \leq k, se minimiza la cantidad de movimientos cuando primero va al borde con la primera posición y luego al borde con la [math]2k-ésima posición. Para hacer esos movimientos se requieren al menos [math]j-1+2k-1 = 2k+j-2 movimientos. Sumando todos los valores de [math]j en este rango, tenemos que se realizaron al menos [math]\sum_{j = 1}^{k} 2k+j-2 movimientos (contaremos todos dos veces hasta el final de la explicación, y luego dividiremos por dos al final).

[math]\sum_{j = 1}^{k} 2k+j-2 = k(2k-2) + \frac{k(k+1)}{2}

Si [math]k+1 \leq j \leq 2k, se minimiza la cantidad de movimientos cuando primero va al borde con la [math]2k-ésima posición y luego al borde con la primera posición. Para hacer esos movimientos se requieren al menos [math]2k-j+2k-1 = 4k-1-j movimientos. Sumando todos los [math]j en rango tenemos que se realizaron al menos [math]\sum_{j = k+1}^{2k} 4k-1-j movimientos.

[math]\sum_{j = k+1}^{2k} 4k-1-j = k(4k-1) - \sum_{j = k+1}^{2k} j = k(4k-1) - \Big( \frac{2k(2k+1)}{2} - \frac{k(k+1)}{2} \Big) = k(4k-1) - \frac{2k(2k+1) - k(k+1)}{2} = k(4k-1) - \frac{k(4k+2 - (k+1))}{2} = k(4k-1) - \frac{k(3k+1)}{2}.

Ahora sumemos los dos resultados obtenidos en la división de casos, para así obtener una cota de la suma total de movimientos en las primeras dos secciones del camino de los [math]j.

[math]k(2k-2) + \frac{k(k+1)}{2} + k(4k-1) - \frac{k(3k+1)}{2} = k(6k-3) + \frac{k(k+1 - 3k -1)}{2} = k(6k-3) - \frac{2k^2}{2} = 5k^2-3k


Ahora sólo nos falta sumar las terceras secciones de los caminos de las fichas. Para ello, es conveniente no pensar en cada ficha individualmente sino pensar que la ficha que al final ocupa el lugar [math]j (que no tiene que ser la que lo ocupaba al principio) tiene que haber hecho al menos [math]min(j-1, 2k-j) movimientos para llegar desde el borde más cercano a [math]j hasta su posición final. Luego sumamos todo esto sobre los [math]j: para los [math]j \leq k, el borde más cercano es el 1 y entonces se acota por [math]j-1. Por el contrario, para los [math]j \geq k+1 el borde más cercano es el [math]2k y luego se acota por [math]2k-j movimientos.

Sumando sobre todos los [math]j posiciones finales queda:

[math]\sum_{j = 1}^k j-1 + \sum{j = k+1}^{2k} 2k -j = 2 \sum_{j = 1}^k j-1 = 2 \frac{k(k-1)}{2} = k(k-1) = k^2-k


Así, finalmente sumamos el [math]5k^2-3k obtenido de las dos primeras partes con el [math]k^2-k de la tercera:
[math]5k^2-3k+k^2-k = 6k^2-4k movimientos como mínimo, pero recordemos que cada uno está contado dos veces (una vez por ficha).

Así, el menor número de movidas es [math](6k^2-4k):2 = 3k^2-2k.

[¿hola?]

Spoiler: mostrar

numeramos la fila de la siguiente manera.
[math]1,2,3,....,2k

miremos que en el lugar [math]1,2 tengo que hacer [math]2k-1 movimientos ya que todas las fichas [math]2,3,4,...,2k tienen que llegar a [math]1.
luego en el lugar [math]2,3 necesito hacer [math]2k-2 movimientos ya que todas las fichas [math]3,4,5,...,2k tienen que llegar a [math]1.
luego en el lugar [math]3,4 necesito hacer [math]2k-3 movimientos ya que todas las fichas [math]4,5,6,...,2k tienen que llegar a [math]1.
y así sucesivamente hasta el lugar [math]k-1,k en donde necesito [math]2k-k-1 movimientos y en el lugar [math]k,k+1 necesito [math]k movimientos.
ahora vemos que las cantidades de movimientos son simétricas respecto de [math]k,k+1 ya que [math]1,2 y [math]2k-1,2k necesito la misma cantidad de movimientos al igual que en los lugares [math]a,b y en los lugares [math]2k+1-b , 2k+1-a ya que todas las fichas necesitaran llegar a [math]1 y a [math]2k
ahora sumemos todos estos movimientos.
[math]2( 2k-1 + 2k-2 + 2k-3 +...+ 2k-(k+1) )+k =
[math]2( 2k(k-1) - \frac{(1+k-1)(k-1)}{2} ) + k =
[math]4k(k-1) - k(k-1) + k = 3k(k-1) + k = 3k^2 - 2k

el ejemplo no es difícil de conseguir.

[Gianni De Rico]

Spoiler: mostrar

[math]3k(k-1)+k=3k^2+2k

Che, le pifiaste un signo al final

Spoiler: mostrar

[math]3k(k-1)+k=3k^2-3k+k=3k^2-2k

[¿hola?]

gracias, ahí lo edito