Pretorneo de las Ciudades - Nivel Juvenil - Problema 3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Pretorneo de las Ciudades - Nivel Juvenil - Problema 3

Mensaje sin leer por Turko Arias »

Se tienen $100$ fichas, numeradas de $1$ a $100$, en una fila. Hay dos movidas lícitas:
Intercambiar dos fichas adyacentes (que estén una al lado de la otra), que cuesta un dólar.
Intercambiar dos fichas que tienen exactamente $3$ fichas entre medio, que es gratis.
Determinar la menor cantidad de dólares necesaria para reordenar las $100$ fichas en el orden inverso al que tenían al comienzo.
1  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Sergiohuang2004

OFO - Mención-OFO 2021
Mensajes: 35
Registrado: Dom 23 Jun, 2019 7:45 pm
Medallas: 1
Nivel: 2

Re: Pretorneo de las Ciudades - Nivel Juvenil - Problema 3

Mensaje sin leer por Sergiohuang2004 »

Me da 54
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: Pretorneo de las Ciudades - Nivel Juvenil - Problema 3

Mensaje sin leer por BrunZo »

Spoiler: mostrar

Yo digo que el mínimo número de dólares a gastar es $50$. Veamos primero que con $50$ dólares se puede invertir el orden.

Primero que nada, vamos a hacer lo siguiente:
Cambiamos el $1$ con el $5$, el $2$ con el $6$, el $3$ con el $7$, y el $4$ con el $8$.
Entonces, el bloque $1,2,3,4$ intercambió posiciones con el bloque $5,6,7,8$.
Ahora, repetimos el procedimiento y cambiamos de posiciones el bloque $1,2,3,4$ con el bloque a su derecha (sería $9,10,11,12$).
Si seguimos así, el bloque $1,2,3,4$ va a terminar a la derecha, mientras que los otros bloques seguirán en el mismo orden.
Pero entonces, podemos repetir el procedimiento con el bloque $5,6,7,8$ para llevarlo justo antes del bloque $1,2,3,4$, y luego el bloque $9,10,11,12$, y así siguiendo. En definitiva, por ahora nos queda:
$$97,98,99,100,93,94,95,96,\dots,5,6,7,8,1,2,3,4$$
Es decir, tenemos la posición de los bloques invertida, pero los números en cada uno todavía no se invirtieron. De todos modos, todavía no gastamos nada.

Ahora es cuando empezamos a gastar:
Consideremos un bloque cualquiera, por ejemplo el $1,2,3,4$. Ahora, vamos a intercambiar de posiciones el $4$ y el $8$, de modo que nos queda $4,1,2,3,8$. Luego, gastamos $2$ dólares, cambiando de posiciones el $1$ con el $4$ y el $2$ con el $3$, de modo que queda $1,4,3,2,8$. Finalmente, intercambiamos gratuitamente el $1$ con el $8$, y resulta $8,4,3,2,1$.
Podemos repetir este procedimiento con los siguientes bloques, de modo que invertimos los números de cada bloque, y el resultado final es la fila entera invertida, gastando sólo $50$ dólares.
(Detalle: Para invertir el último bloque tenemos que tomar el número a la derecha en vez de a la izquierda, es decir $97,98,99,100,96$ lo reemplazamos por $96,98,99,100,97$, cambiamos por $96,99,98,97,100$ y finalmente por $100,99,98,97,96$).


Bueno, ahora vemos que siempre necesitaremos al menos $50$ dólares para conseguir nuestro objetivo:
Decimos que una ficha está en la categoría $0$, $1$, $2$, o $3$ dependiendo del resto en la división por $4$ de la posición de la ficha, contada desde la derecha. Por ejemplo, al comienzo la ficha $27$ está en la categoría $3$.
Notemos algunas cosas:
  • La operación gratuita no cambia la categoría de ninguna ficha, puesto que intercambia la posición de dos fichas de la misma categoría.
  • La operación de $1$ dólar cambia la categoría de exactamente dos fichas.
  • En las distribuiciones inicial y final, ninguna ficha preserva su categoría (de hecho, todas las fichas de la categoría $1$ pasan a la categoría $0$ y todas las de la categoría $2$ pasan a la categoría $3$).
Es decir, entre las distribuciones final e inicial necesitaremos cambiar la categoría de las $100$ fichas, y sabemos que con $1$ dólar cambiamos a lo sumo la categoría de $2$ fichas, luego necesitaremos al menos $50$ dólares, como queríamos.

Como ejercicio al lector queda hacer sentido del ejemplo a partir de este argumento.
2  
lleandro
Mensajes: 7
Registrado: Lun 12 Feb, 2018 1:20 pm

Re: Pretorneo de las Ciudades - Nivel Juvenil - Problema 3

Mensaje sin leer por lleandro »

Simplifiqué el problema, junto con la idea de maximizar los intercambios con 3 intermedios, y sólo usar el intercambio adyacente para lograr llegar al otro extremo. Empezando por el uno, luego con el dos y así sucesivamente, una vez que se llega a la mitad la otra mitad se ordena automáticamente.
Luego si el procedimiento se aplica a 100 no varía el costo por mover a uno por dolar cada número, siendo sólo necesario movilizar la mitad de los números, por tanto se necesitan 50 dolares como mínimo. Adjunto imagen donde los que están en color verdes son movimientos gratis a futuro, y los amarillos los de costo 1 dolar.
Responder